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=SUu 7 for each vertex v G.Adjlu] 8 RELAX(.v.w) 初始阶段(Initialization): -S=0,不变式显然成立 0 运行期间(Maintenance): We wish to show that in each iteration,u.d =o(s,d)for the vertex u added to set S. ·终止时刻(Termination) Termination:At termination,=0 which,along with our earlier invariant that O=V-S,implies that S=V.Thus,u.d =8(s,u)for all vertices u V.Dijkstra算法 正确性 • 初始阶段(Initialization)： – 𝑆 = ∅, 不变式显然成立 • 运行期间(Maintenance): – We wish to show that in each iteration, 𝒖. 𝒅 = 𝜹(𝒔, 𝒅) for the vertex 𝒖 added to set S. • 终止时刻(Termination)