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/
