I need more time. I do not have time for this. These are probably the two sentences that we use the most these days. It has often been observed that time is money -- and accomplishing a task in fewer steps can save time (and thus money). With graphs, this can be expressed as finding the shortest path, and has a number of practical applications. This eighth part of a 13-part article series on graphs takes a close look at ways to solve this common problem.
Contributed by Gabor Bernat Rating: / 3 May 27, 2009
The following practical problem occurs. A new public person transport company arrives in town. They have a central bus station. They make a little survey in the town to determine which streets would have more clients. Now, given this favorable rate information about each street, we need to build the optimal routes, so we make the most cash with the least investment.
Another chapter in my series about graphs starts here. In this and the next part, the central problem concerning us will be to determine the minimal road between vertexes inside graphs (therefore for everything that may be represented by graphs). Today we are going to examine two methods, leaving two more for a future article.
Today we you will learn about Dijkstra’s Algorithm and the minimal road calculation based on topological order. Next time we will determine the same thing using the Bellman-Ford technique and the Roy-Floyd algorithm. Nevertheless, so you can understand what we will be discussing today, you should start with some basic knowledge that I already covered in my earlier articles.
First, you need to know the definition of graphs and trees, and how we can represent them in our programs (read An Insight into Graphs). Second, you should be familiar with the concepts like the fundamental circle system and the topological sort. For this you may want to read my articles entitled Circles and Connectivity in Graphs and Depth-First Search in Graphs.
When you have a general grasp of these concepts, you may read on. For solving the problem, we will use an array of n items where index v will show us the distance between the points from where we search for the minimal road to the others. In the future, we will refer to this as the root vertex (you will see why later).
Therefore, if the v is our root vertex, at index v in our array, it will be zero, as we already are in that point and no longer need to make any future steps; the distance is zero accordingly. If there exists no road between the root vertex and index, v the distance is infinity. In our programming world, we will settle for an INT_MAX divided by two (so we can add these up).
By definition, if there is a circle whose overall weight is negative, the distance of the points related to the circle is minus infinity. This is obvious, as we can always make a shorter path by just making another lap around the circle, eventually finishing up at minus infinity. The approach used by all of the algorithms I am going to show to you is the gradual approximation.
Strangely enough, there is no algorithm that can tell us just the shortest road between two points. All of the techniques calculate the minimal road from a single source to all the other vertexes. At least no mathematician has found a way to this day, so feel free to look into building your own.
The gradual approximation reuses the fundamental of optimality. This implies that a shortest paths sub-road is also shortest road. This means, to put it simply, that if the shortest road from Berlin to Paris is via Luxembourg, then the road between Paris to Luxembourg is also a shortest route.
From this comes three conclusions. One is the fact that, from roads containing fewer edges, we can build longer ones (so if we find that the road from Paris to Luxembourg is a shortest one, we can determine from this, eventually, the shortest road from Paris to Berlin).
Second is that the result will be a tree whose root is the source vertex. All of the following algorithms somehow build the roads as a tree growing out from the source vertex at each step, adding another edge to the tree. The minimal roads will form a tree, and the solution in the end will be a tree, and from this it follows that it will contain n-1 edges.
The third conclusion is the following equation, where SR is an acronym for Shortest Road:
SR(s, v) = SR(s, u) + SR (u, v)
Moreover, the algorithm solving the problem may be summed up in the following steps. First, we start from the array of distances where we guesstimate the distance to the other vertexes to infinity. The root from the source vertex to the source vertex is zero.
We will make gradual approximations to the best solution systematically by checking the following expression and applying it if the idiom turns out to be true:
if (distance[v] > distance[u] + edgeDistance[u] [v])
{
distance[v] > distance[u] + edgeDistance[u] [v];
ancient[v] = u;
}
The edgeDistance two-dimensional array is a weight matrix that in fact contains the weight of the edges. If there is no edge between two vertexes, this will be infinity. Now you can see why we need to define infinity as something that allows us to add infinity to infinity.
The upper step is to be repeated until we build a tree, at which point, from the parent array, we can also tell through which points our shortest road travels. At every approximation, we will add another edge to the tree.
The trick is to make these approximations in the right order and at the right time. The following three algorithms (two in this article and one in the next) differ only by how they find the right order in which to make these approximations. They are different because they solve another problem, and need to take into account another complication factor, as we will see as we examine the techniques.
What I am talking about is that, depending on the type of the graph, we can make algorithms that are more efficient. The Bellman-Ford algorithm will solve all the graphs (well, at least those for which the minimal road exists – aka no negative circles inside them). However, this may turn out to be too slow -- in a programming contest, for instance.
The topological order-based technique and Dijkstra’s algorithm will try to perform approximations with each edge at most once, while the Bellman–Ford (and the Roy-Floyd) approaches may need to recheck edges more than once.
The topological order-based algorithm is defined for graphs where the topological order exists. Therefore, we must not have circles inside our graph. We can check this easily by finding only a single back-pointing edge during the Depth-First Search algorithm, as I explained in the article dedicated to this topic. Additionally, we should not have any negative edges.
This will sort the vertexes in an order in which all the edges point from the left to the right, as you may see in the example below:
We start out from the root vertex of the upper sort order. All the vertexes prior to the root will remain with a distance of infinity, as we cannot step backward. Now we need to make the approximations for the edges ahead. The ideal would be to approximate for a vertex when an approximation has been made through all of its incoming edges.
The topological order allows us to do this. There are no edges pointing backwards, so all we need to do is to make the approximation in topological order. At every vertex (starting from the source), we make the approximation through all of its forward-pointing edges (in this case, all of the vertexes are of this kind).
Now, when we arrive at a vertex, we've already drawn through all the incoming edges, and the shortest distance to that vertex is already calculated. We can build the next edge of the tree further on.
The complexity of this algorithm is O (n+m). The technique explained above is one that builds the future by checking the outgoing edges. However, it can be made into an algorithm that will check all of the incoming edges, therefore looking back in the past. For this, we will need to invert the edges' direction in the distanceEdges matrix; this I will leave for you to build, if you wish. I have written the code snippet for the upper approach; it looks like this:
void topologicalAlgorithm (int root)
{
int i = 0;
pListIt p;
int u;
for (i = 1; i <=n; ++i)
{
distance[i] = INT_MAX/2;
ancient[i] = 0;
}
distance [root] = 0;
ancient [root] = 0;
for (i = 0; i <n; ++i)
if (topological[i] == root)
{
break;
}
for (; i <n; ++i)
{
u = topological[i];
for (p = vertexList[u]; p != NULL; p = p -> p_next)
if (distance[u] + adiacentMatrix[u] [p->value] < distance [p->value])
This algorithm is for graphs where circles do exist; nevertheless, the edges are all positive. To imagine what negative edges mean, consider the following problem. Joe wants to travel home from Berlin to Paris. Consider that the cost of the travel depends only on the distance. The shortest road may be via Luxembourg in this case. However, if Joe wishes to visit his grandma in Brussels, he will want a cost-effective routing, but it will be less cost effective than if he went directly home.
Dijkstra’s Algorithm may be familiar to those who have already read my article about minimal spanning trees and in particular Prim’s Algorithm. The only difference is that, while Prim’s Algorithm tries to extend the tree with minimal edges between the graph and the tree that they build, Dijkstra’s Algorithm will extend the tree with the minimal distance (the sum of roads) of the vertexes from the source and the edges connecting the graph and the tree we create.
So while Prim just takes the minimum distances between the edges that were at the point connected only with one edge to the graph, Dijkstra will add to these edges the current road of the vertexes to the source, and search for the shortest route between these.
For those of you who failed to read that article, I need to explain further. The idea is to build the tree. At the start, we have inside the tree only the source vertex. Now we search for the edges that are connected to the source and elect the shortest one.
At the next step, we will search for edges that are not forming a circle, and will form a minimal road to the source vertex between those we can choose. These edges will connect our tree with the rest of the graph, making their place inside a cut that divides the two.
Edges will make their place in the cut as soon as one of their vertexes becomes part of the tree, and get out of the cut when the other end also becomes part of our tree. To simulate this, we will build a queue of the edges that are still not connected to the tree.
We will only treat edges that have one edge in the queue and another outside it, and from this choose the one that will form the minimal road to the source. In addition, we will treat only edges whose direction points outside of our tree; all inside-pointing edges shall be ignored. In the end, the points that remain in the queue cannot be reached from the source vertex.
Why does Dijkstra’s algorithm also solve graphs within which we have circles? Because here the edges that form the problem are the back-pointing edges. However, for this they will first have the end of their edge added to the tree. Let there be, for the edge, a directed one starting from vertex u and pointing towards v. The distance between v and u is infinite, and therefore the road between source and v will remain infinite.
By the time the u vertex is part of the tree, the v is also, though this edge will never make it into our cut edges. The algorithm will simply ignore any back-pointing edge and ignores circles. We can do this because the circle would anyhow just increase our distance to the source, given that the backward-pointing edge is not negative. If this turns out to be negative, our assumption will collapse, and for the solution we'll need to use the Bellman-Ford Algorithm. Here it is, Dijkstra’s Algorithm implemented in something close to C:
void DijkstraAlgorithm (int root)
{
int i = 0;
pListIt p;
int cur;
qsort ((void*) edges, m, sizeof (edge), compare);
for (i = 1; i <=n; ++i)
{
distance[i] = adiacentMatrix [root] [i];
if (distance[i] == INT_MAX/2)
{
ancient[i] = 0;
}
else
ancient[i] = root;
}
distance [root] = 0;
ancient [root] = 0;
// build up the queue
int *queueD; // Inside this array we will generate the
queueD = (int*) calloc (n+1, sizeof (int));
// Put inside the queue the root
queueD [root] = 1;
int j = 0;
// start
for (;;)
{
// Select next vertex
cur = 0;
for (j =0; j < m; ++j)
{
if (queueD [edges[j].from] && !queueD [edges[j].to])
{
cur = edges[j].to;
break;
}
}
// if none find => no available vertex
if (! cur)
{
break;
}
// ok cur will be added queueD the array
queueD [cur] = 1;
for (p = vertexList [cur]; p != NULL; p = p -> p_next) // now look through all of the list
The algorithm that is the opposite of the topological order-based one works for graphs with no directed edges inside them. Here there will be no back-pointing edges, and through all edges, the algorithm will try to approximate the distance from the source to a certain vertex. At every approximation, we can also store the parent of the vertex inside the tree, and in the end use a simple recursion to find out the roads vertex by vertex. The complexity of the algorithm, given that we implement our queue with a binary heap, can turn out to be an O (m*lg (n)).
By clicking on the link above, you may download all this expressed as a C file. There I have resolved problems such as reading in and printing out the result (including the vertexes through which the roads lead). I also and added a little extra to it: a Depth-First Search Algorithm that will check for the correct algorithm to apply and call that. It is commented at every step, so I am confident that you will understand it.
Thank you for reading my article. I would like to encourage you to rate my article or post your thoughts about its content or improvement advice here on the blog. Alternatively, you may join our friendly ever-growing forum over at DevHardware and ask your question there from out experts. Come back next time, when we will continue this topic with the algorithms of Bellman-Ford and Roy-Floyd. Live With Passion!
Code Examples 
The Bellman-Ford and Roy-Floyd Algorithms
