DIJKSTRA(G.w.s) 1 INITIALIZE-SINGLE-SOURCE(G.S) 2 S=0 3 O=G.V Dijkstra算法正确性 4 while O≠g 5 EXTRACT-MIN(O) 6 S=SUfu 7 for each vertex vE G.Adjlu] 8 RELAX(u.V.w) Theorem 24.6(Correctness of Dijkstra's algorithm) Dijkstra's algorithm,run on a weighted,directed graph G=(V,E)with non- negative weight function w and source s,terminates with u.d =8(s,u)for all vertices u e V. Proof We use the following loop invariant: At the start of each iteration of the while loop of lines 4-8,v.d 8(s,v) for each vertex v∈S. It suffices to show for each vertex u E V,we have u.d =8(s.u)at the time when u is added to set S.Once we show that u.d =8(s.u),we rely on the upper-bound property to show that the equality holds at all times thereafter.Dijkstra算法 正确性