The solution was published by Richard E. Bellman and Lester Ford, Jr. in 1958 in their publication “On a Routing Problem” and it is quite simple to explain and understand. Since we can prioritize the edges by its lengths the only thing we should do is to calculate all the paths. And to be sure that our algorithm will find all the paths correctly we repeat that N-1 times, where N is the number of vertices (|V| = N)!
The algorithm of Bellman-Ford doesn’t use priority queues! Indeed they are useless since the closest node in the queue can have shorter path passing through another node!
In this very basic image we can see how Bellman-Ford solves the problem. First we get the distances from S to A and B, which are respectively 3 and 4, but there is a shorter path to A, which passes through B and it is (S, B) + (B, A) = 4 – 2 = 2.
Read full article from Algorithm of the Week: Bellman-Ford Shortest Path in a Graph | Javalobby
No comments:
Post a Comment