微信图片_20190501112123.jpg
微信图片_20190501112316.jpg
微信图片_201905011121231.jpg
微信图片_201905011121232.jpg
微信图片_201905011121233.jpg
微信图片_201905011121234.jpg
微信图片_201905011123161.jpg
微信图片_201905011123162.jpg
def Dijkstra(v, G[1..n]):
# O(n)
dist[1..n] filled with inf
dist[v] = 0
finalized[1..n] filled with False
while something is not finalized:
# O(n)
u = not finalized with the smallest distance
# O(1)
finalized[u] = True
# O(m)
for (w, l) in G[u]:
# O(1)
dist[w] = min(dist[w], dist[u] + l)
return dist
Complexity
O(n+1)n+O(n)+O(m) = O(n^2)
failed if negative edges
def bellmanford(v, G[1..n]):
# O(n)
dist[1..n] filled with inf
dist[v] = 0
for i from 1 to n-1:
# O(n)
ndist = dist.deepcopy()
# O(n+m)
for u from 1 to n:
for (w,l) in G[u]:
ndist[w] = min(ndist[w], dist[u]+l)
# O(n)
dist = ndist.deepcopy()
return dist
Complexity
O(n) + n(O(m+n)) = O(nm+n^2)
Floyd-Warshall
In: Graph G
Out: dist[1..n][1..n]
dist[u][w] from u to w
Look[k,u,v] = # the length of the shortest path from u to w s.t the inner vertices on the path are from 1 to k (path中间的vertices)
Look[n,,] -- answer
Look[0,u,v] = l if uv are neighbors or inf otherwise
Look[k+1,u,v] = min(Look[k,u,v], Look[k,u,k+1]+Look[k,k+1,v])
