Last Updated: 2024-05-01 03:47:11 Wednesday
-- TOC --
最短路径问题，SP，Shortest Path。
Shortest是指某种Weight或Cost的最小化，Shortest Path一定是无环的：
因此，只要source无法达到负cost环路，Shortest path is Well Defined。
下面是两种求解SP的递归视角，s起点，t终点：
$$SP(s,t)=min_{v\in NRB(s)}\{w(s,v)+SP(v,t)\}$$
$$SP(s,t)=min_{u\in NRB(t)}\{SP(s,u)+w(u,t)\}$$
可以看出，SP问题符合动态规划问题特征，optimal substructure and overlapping subproblems，可以用DP的方法求解。但使用DP算法的复杂度是很高的。当SP问题存在时，肯定无环，每个顶点也是经过一次，用DP解的时间复杂度与TSP问题相同：\(O(n^2\cdot 2^n)\)。
在Unweighted Graph的情况下，SP就是Edge数量最少的路径。
Bellman-Ford算法参考实现如下，连同测试代码：
import random
random.seed()
import time
N = 4
Edge = [[0]*N for _ in range(N)]
for i in range(N):
for j in range(N):
if i == j:
Edge[i][j] = None
else:
Edge[i][j] = random.randint(-10,10)
Edge[i][j] = None if Edge[i][j]<-4 else Edge[i][j]
print('Node number', N, ', Edge matrix:')
for i in range(N):
for j in range(N):
print(str(Edge[i][j]).center(5,' '), end=' ')
print()
def bellman_ford(s):
assert s < N
# distance from s to others
dist = [None] * N
dist[s] = 0
# iterate all edges N-1 times
for k in range(N-1):
td = dist[:]
for i in range(N):
for j in range(N):
if Edge[i][j] is None:
continue
if td[i] is not None:
if td[j] is None or td[j]>td[i]+Edge[i][j]:
dist[j] = td[i] + Edge[i][j]
# False: negative cycle, SP is not well defined
for i in range(N):
for j in range(N):
if Edge[i][j] is None:
continue
if dist[i] is not None and dist[j] is not None:
if dist[j] > dist[i] + Edge[i][j]:
return False, dist
return True, dist
for i in range(N):
print(i,bellman_ford(i))
N个节点的Graph，从一个点到另一个点，最多经过N-1条边。因此，如果循环N-1次后，能够到达的节点就都找出来了，并且是最短路径。此时如果再遍历一次Edge，如果还能够Update，就说明存在Negative Cycle。
对于Undirected Graph来说，只要有一条Edge是负的，就是存在Negative Cycle了！
使用Bellman-Ford算法探测是否存在Negative Cycle，需要指定一个Source节点，如果这个Source节点与Negative Cycle之间没有通路，就不能实现探测。而且，Bellman-Ford算法无法探测回到source的Negative Cycle（此时可以考虑Floyd-Warshall算法）。
复杂度：\(O(VE)\)
import random
random.seed()
import time
N = 6
Edge = [[0]*N for _ in range(N)]
for i in range(N):
for j in range(N):
if i == j:
Edge[i][j] = None
else:
Edge[i][j] = random.randint(-10,10)
Edge[i][j] = None if Edge[i][j]<7 else Edge[i][j]
print('Node number', N, ', Edge matrix:')
for i in range(N):
for j in range(N):
print(str(Edge[i][j]).center(5,' '), end=' ')
print()
def dag_sp(s):
assert s < N
tpsort = []
visited = []
def __dfs(v):
visited.append(v)
for i in range(N):
if Edge[v][i] is None:
continue
if i in visited:
continue
__dfs(i)
tpsort.insert(0, v)
__dfs(s)
assert s == tpsort[0]
dist = [None] * N
dist[s] = 0
for v in tpsort:
td = dist[:]
for i in range(N):
if Edge[v][i] is None:
continue
if td[i] is None or td[i]>td[v]+Edge[v][i]:
dist[i] = td[v] + Edge[v][i]
return tpsort, dist
print(dag_sp(0))
复杂度：\(O(V+E)\)
可能有环存在，就无法计算Topological Sort。
Dijkstra算法其实就是更一般化的BFS，只是Dijkstra没有使用Queue来控制访问vertex的顺序，而是采用Heap（Priority Queue）。因为计算Path不再是简单的数Edge的数量，Edge有了Weight/Cost。可以把BFS看做是Dijkstra的特例。Dijkstra算法即体现了Dynamic Programming思想，也包含了Greedy基因。它的计算过程，通过Greedy选择每一步的最优解，同时每一步也是求解一个subproblem。
Dijkstra(s): # find shortest path to all other vertice from s
S = {s}
MH is a minheap # (edge,pathcost),pathcost is the key
add all (x,cost of (s,x)) to MH if x is neighbor of s
while |S| != |V|:
extract the minimum from MH as (y,pc)
S = S + {y} # shortest path from s to y is determined as pc
# maintain MH
for each y's neighbor as z:
if there is a path to z in MH:
update to (z, min(pc+w(y,z),orignal cost value))
else:
add (z,pc+w(y,z)) to MH
heap中元素的最大值为|V|，每个vertex都要进去并出来一次，每个edge都要被用来update一次，因此复杂度：\(O((V+E)\log V)\)
算法是个数学模型，抽象成Graph后，可能存在Negative Edge的情况，因此就可能存在Negative Cycle。判断Graph中是否存在Negative Cycle，就成了一个问题。
基于前文的内容，判断Negative Cycle有如下算法：
其实，以上两个算法都是用来计算SP的，但都可以变相用来判断Negative Cycle问题！
本文链接：https://cs.pynote.net/ag/graph/202403192/
-- EOF --
-- MORE --