Bellman-Ford: Efficient ImplementationPush-Based-Shortest-Path(G, s, t) {foreachnodeveViM|v]= 00successorvl= empty1M[t] = 0fori= 1 to n-1 foreachnodeweVif (MJwl has been updated in previous iteration)for each node v such that (v, w)"E if (M[v] > M[w] + cvw) (M[v] = M[w] + cvwsuccessorv=w14If no M[w] value changed in iteration i, stop.2chapter25
Bellman-Ford: Efficient Implementation Push-Based-Shortest-Path(G, s, t) { for each node v V { M[v] = successor[v] = empty } M[t] = 0 for i = 1 to n-1 { for each node w V { if (M[w] has been updated in previous iteration) { for each node v such that (v, w) " E { if (M[v] > M[w] + cvw) { M[v] = M[w] + cvw successor[v] = w } } } If no M[w] value changed in iteration i, stop. } } chapter25
Vu-2-3Z-4xy(a)chapter25
-2 -3 -4 z u v x y (a) chapter25
Vu-2-3Z-4xy(b)chapter25
-2 -3 -4 z u v x y (b) chapter25
vu-2-3z-4xychapter25
-2 -3 -4 z u v x y chapter25