Correctness Theorem. IfG=(V, E) contains no negative weight cycles, then after the Bellman-Ford algorithm executes, d[v=8(s, v) for all vE v. Proof. Let ve v be any vertex, and consider a shortest path p from s to y with the minimum number of edges p:(Vo Since p is a shortest path, we have 6(S,v)=8(s,v21)+w(v21,v) c 2001 by Charles E Leiserson Introduction to Agorithms Day 31 L18.13© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.13 Correctness Theorem. If G = (V, E) contains no negative￾weight cycles, then after the Bellman-Ford algorithm executes, d[v] = δ(s, v) for all v ∈ V. Proof. Let v ∈ V be any vertex, and consider a shortest path p from s to v with the minimum number of edges. v1 v1 v2 v2 v3 v3 vk vk v0 v0 … s v p: Since p is a shortest path, we have δ(s, vi) = δ(s, vi–1) + w(vi–1, vi)