CODEWITHSUNDEEP
algorithmgraph-algorithmbellman-ford
shahalpk
shahalpk

Reputation: 3452

Why no relaxing of all edges in the first iteration of Bellman Ford Algorithm?

Please refer to the following page for Bellman ford algorithm (it shows an e.g). http://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm

I still don’t get it. In the first loop iteration of the outer loop, let’s say by the example, u first modify edge 1->2 and edge 1->4, what’s the problem in relaxing the edge 2->3, 2->5, 4->3, 4->5,in the same step, since we have d[2] and d[4].

Upvotes: 0

Views: 1066

Answers (1)

hugomg
hugomg

Reputation: 69934

This problem magically disappears if you use a sligtly different version of Bellman-Ford:

set toRelax = {initial_vertex}
while toRelax is not empty:
    u = remove a vertex from toRelax
    for each neighbour v of u:
       if we can relax u-v:
          relax u-v
          add v to toRelax

Notice how each "step" now involves a single vertex! Things being done in the "same step" or not are just an artifact of the specific implementation you use and don't really change the algorithm in the end.

Upvotes: 1

Related Questions