2 2 votes Hi Guys, As everyone knows Bellman Ford Algorithm works on DP approach. The algorithm calculate shortest paths in bottom-up manner. It first calculates the shortest distances which have at-most one edge in the path. Then, it calculates shortest paths with at-nmost 2 edges, and so on. After the i-th iteration of outer loop, the shortest paths with at most i edges are calculated. There can be maximum |V| – 1 edges in any simple path, that is why the outer loop runs |v| – 1 times. Now my question is --> Should we follow same edge sequence in all iteration or Following some random edge sequence in each iteration will increase number of iteration required to find shortest path. But i think in any case |V| iterations are enough (where V is number of vertices). I think if we will follow same edge sequence in all iteration then in some special cases algorithm may converge faster. What is your opinion ? Refer --> http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/ Algorithms algorithms shortest-path bellman-ford graph-algorithms + – Chhotu 1.1k views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
