The Bellman-Ford and Roy-Floyd Algorithms
(Page 1 of 4 )
Everyone wants to get the most out of their investments. When you make a sacrifice and get yourself involved in something, then most of the time, you want in return every little drop you can stroke out of the situation. When you cannot influence this, it is time to find a way to invest/sacrifice only as much you absolutely need to. If your problem can be summed up as a graph, and the shortest path is your solution, then you came to the right place. This is the ninth article in a 13-part series on graphs and how they can be used for problem solving.
The problem is simple: why waste time and gasoline when you are traveling by taking a longer route when you have the option to arrive in the same place, and earlier, by way of a different path taken to the destination? This is the second article of my series that specifically covers how to calculate the shortest paths between points.
During our last article, entitled suggestively "Shortest Path Algorithms in Graphs," we found two solutions for the single-source shortest-path algorithms. The first works only if we have no circle in the graph, as otherwise we cannot topologically sort the vertexes of the graph. The second works as long as we do not have negative edges, as the algorithm is able to ignore the back-pointing edges that formed the circle.
We may ignore the algorithm, however, only if there are no negative edges, because traveling in the opposite direction, the circle might shorten the distance. Today the Bellman-Ford algorithm is going to help us in situations when we have negative edges inside our graph. However, we cannot have fundamental circles with an overall negative weight sum.
In this case, the distance between the vertexes is not defined, or they are defined, at minus infinity, as we may circle there infinitely and at every circuit decrease the distance more and more. Afterward we are going to learn a method to calculate the minimal distances between every point of the graph and to find out where this minimal road leads.
Next: The Bellman-Ford Algorithm >>
More Code Examples Articles
More By Gabor Bernat
