DIJKSTRA(G.w.s) 1 INITIALIZE-SINGLE-SOURCE(G.S) 2S=0 3 0=G.V Dijkstra算法正确性 4 while O≠0 5 EXTRACT-MIN(O) 6 S=SUfu 7 for each vertex vE G.Adjlu] 8 RELAX(u.V.w) Corollary 24.7 If we run Dijkstra's algorithm on a weighted,directed graph G =(V,E)with nonnegative weight function w and source s,then at termination,the predecessor subgraph G is a shortest-paths tree rooted at s. predecessor-subgraph property 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.Dijkstra算法 正确性 predecessor-subgraph property