证明y.d=6(s,y)=(s,d)=u.d Convergence property (Lemma 24.14) If suv is a shortest path in G for some u,vV,and if u.d 8(s,u)at any time prior to relaxing edge (u,v),then v.d =8(s,v)at all times afterward. ·y.d=6(s,y) Convergence property x.d=6(s,x) when x is added to S Edge (x,y)was relaxed y.d=6(s,y) P是s→u最短路径 >p1+(x→y)是s→y最短路径 y.d 8(s,y) ≤ 6(s,) y.d=6(s,y) P2 ≤ u.d =6(S,d) u.d u.d≤y.d Dijkstra算法保证证明𝒚. 𝒅 = 𝜹 𝒔, 𝒚 = 𝜹 𝒔, 𝒅 = 𝒖. 𝒅 • 𝒚. 𝒅 = 𝜹 𝒔, 𝒚 when 𝑥 is added to 𝑺 𝒙. 𝒅 = 𝜹 𝒔, 𝒙 Edge 𝒙, 𝒚 was relaxed P是𝑠 → 𝑢最短路径 𝒚. 𝒅 = 𝜹 𝒔, 𝒚 Convergence property 𝒚. 𝒅 = 𝜹 𝒔, 𝒚 = 𝜹 𝒔, 𝒅 = 𝒖. 𝒅 𝑝1 + (𝑥 → 𝑦)是𝑠 → 𝑦最短路径 Dijkstra算法保证