Let G = (V,E) be a directed graph with non-negative edge costs c(e). Let s V be a starting node for shortest paths. Prove that for any graph this algorithm will converge in finite time to the correct shortest path values.

= = 3 i d(s) = 0, d(u) o for all v + s, p(v) = s 2 while there is an incorrect edge (u, v) do correct it: d(v) + d(u) + c(u, v) p(v) u 6 Output the d(v)'s 4 5