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.
Contributed by Gabor Bernat Rating: / 1 May 28, 2009
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.
The Bellman-Ford technique continues the gradual approximation approach. If you missed my last article, I invite you to search it up and read it, as I will not explain again what is this all about and how it will help us in understanding and solving the problem.
While using the topological order-based approach and Dijkstra's Algorithm we found some ways to determine the right arrangement of the edges so that we may make the approximation when we need it. When a negative edge is also present in our graph, with circles whose sums remain positive, we can no longer find an order like this.
Therefore, we can no longer guarantee a single approximation with the edges. We will take the list of the edges and call the approximation algorithm as many times as an approximation is made. When we try to improve our distance array with each of the edges, and none can be made, we have finished the shortest path algorithm.
In the best-case scenario, this will lead to a single call. This is the case when all the edges are in the order they would be in the tree that builds the solution. This time, the solution is a tree whose root vertex is the source node from where we want to calculate the roads.
However, what is the limit of the maximal call, so that we do not enter into an endless loop? At the first call, the algorithm will solve the shortest path with the length of one edge. Further on, this will find the shortest roads containing two edges, and so on.
In the end, our tree must have n-1 edges, therefore executing the approximation through all edges n-1 times guarantees that we will get a good solution. If we do not know whether or not our input has negative circles, we can perform the approximation attempt once again on the graph (n-th time), and if it makes a single approximation, this will reveal a negative circuit.
The complexity is O (n*m), including the negative circuit fail-proof detection system. This will offer a result to any graph; however, this can turn out to be painfully slow.
The complexity of the topological order-based approach is O (n+m), and Dijkstra's Algorithm is O (m*lg (n)), so there is little competition if you want to solve a problem as fast as possible, and you know extra information, like the graph's contents include no circle or no negative edges. The parent-saving mechanism remains, so with a simple recursion we can print the roads as well. Here is the code snippet:
void BellmanFordAlgorithm (int root)
{
int i = 0;
int l;
int itwasMod = false;
for (i = 1; i <=n; ++i)
{
distance[i] = INT_MAX/2;
ancient[i] = 0;
}
distance [root] = 0;
ancient [root] = 0;
int k = 1;
do
{
itwasMod = false;
for (i = 1; i <= n; ++i)
{
for (l = 1; l <= n; ++l)
{
if (distance[i] + adiacentMatrix[i] [l] < distance[l]
&& distance[i] != INT_MAX/2
&& adiacentMatrix[i] [l] != INT_MAX/2) // Infinity plus/minus something is still infinity
The previous algorithm's goal was to determine the shortest path from a source vertex to all the other vertexes. Now we are going to calculate the shortest paths between all the nodes inside a graph. The technique, also variously known as Floyd's algorithm, the Roy-Warshall algorithm, the Roy-Warshall algorithm, or the WFI algorithm is an extension of the Bellman Ford algorithm to the whole graph and all the vertexes.
The only prerequisite of this algorithm remains that the graph should not contain any negative circuits. You can perceive the algorithm as similar to the earlier approach, but now we are going to build n trees simultaneously, and each one of them will contain in the end the shortest path from a vertex to all the others.
We will switch our array of distances to two-dimensional arrays that at the start will be the same as the weight matrix. Therefore, we will guesstimate that the shortest road between two vertexes is the edge connecting them if it exists, infinity if there are no edges connecting and zero between the same vertexes.
This is the initial start of the matrix. Now on this matrix we are going to make the approach n times, which is similar to how we made it with of Bellman-Ford. At step k, we are going to build the distance matrix from the k-1 state. Starting from the simple, trivial solution, we are going to create a more complex solution.
This method is well known under the name of the dynamic programming technique. At each step, we will check if the "k" vertex is on the shortest road between "i" and "j". If the answer is yes, we do not need to make any further approximations; otherwise, we will make this part of the road by adding the current known shortest road between "i"-"k" and "k"-"j".
This is true because the shortest road is built from the sub-shortest roads. In addition, if we know the shortest road between edges "i"-"k" and "k"-"j" then we can conclude that "i"-"j" is the shortest road between node "i" and "j".
We need to repeat this n times, and the solution is complete. At each step, at least one shortest road will be determined, so at the end of n steps, all of the graph's shortest roads should be calculated.
The complexity of all this, due to the fact that we make n iterations on the distance matrix, which is also of a size n X n, will be O (n^3). This is quite bad, so unless you need all of the roads and shortest paths, avoid using it. We can determine whether we have negative circles in the graph in two ways.
We can observe that if, on the main diagonal after the n iteration, we can find a negative number (meaning that there is a road between "i" and "i" less than zero), we have a negative circle. Or, as in the case of the Bellman-Ford algorithm, we can run the approximation approach again and observe whether or not another change is made. The code snippet should look like this:
The road between the edges can also be stored during the run time; all we need to do is store the parent of the item where we made an approximation. I already told you that we could perceive the algorithm like the construction of n trees at the same time. The solution from a point will still be a tree with n-1 edges. Because of this, it is possible to store all this inside one array of size n X n.
In this two-dimensional array I am going to store in the k-th row the parent array of the solution. However, we cannot talk of multiple trees at the same time inside a graph, so we are going to switch all this to storing the vertex before the last in the position "i" and "j" of the array. If you think about this a little, you will realize that this is the same in the end.
For our approach to work, we need to initialize our array, that I named priorAncientV, according to the state of our matrix at the start. As we guesstimated the direct edge, if there is a direct edge from "i" to the vertex "j" the later node will be in our matrix at the position "i" , "j" (before node "i" there is the node "j").
During the algorithm, if we find a shorter road between two vertexes via the node "k", derive there the new shortest road, as you can see on the previous page. After the Roy-Floyd technique, running down a simple recursion on the row "i" of the priorAncientV matrix will reveal to us where the roads go through. All we need is a simple recursion, as you will see in the code snippet below:
printf ("nn The roads between the edges: n");
for (i = 1; i <= n; i++)
{
printf ("n");
for (j = 1; j <= n; j++)
{
if (distances[i] [j] == INFINITY)
{
printf ("Infinity ");
printf (" ~~~ %d => %d ~~~", i, j);
}
else
{
printf ("%d ", distance[i] [j]);
printf (" ~~~ %d => %d ~~~", i, j);
recursion (priorAncientV[i], j);
printf (" %d ", j);
}
printf ("n");
}
}
void recursion (int*& arrayPV, int j)
{
if (j && arrayPV [j])
{
recursion (arrayPV, arrayPV [j]);
printf (" %d ", arrayPV [j]);
}
}
Today, as a download, I am going to add to this article both the one already present in the previous article, as now we also understand the Bellman-Ford approach, and a new one presenting the Roy-Floyd approach. Both sections of code are quite easy to read, and I am confident that you will have no difficulties in comprehending it fully if this article left any doubts.
With this, we finished the shortest road problem in graphs. Now you should be able to solve shortest path issues efficiently from a single source or between all the vertexes of a graph. At our next meeting, I will present the concept of critical paths and of course, pair it with some C code in what I will show how you can find them.
Thank you for reading through this second part of my two-part article related to the shortest paths in graphs. Moreover, I would like to encourage you to rate my article, comment it here on the blog or join the DevHardware forums and act in the same manner there. Live With Passion!
Code Examples 
Shortest Path Algorithms in Graphs
