Shortest Path Algorithms in Graphs - The Topological Order-Based Algorithm
(Page 3 of 4 )
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])
{
ancient [p->value] = u;
distance [p->value] = distance[u] + adiacentMatrix[u] [p->value];
}
}
// Once finished print the result
printResult ();
}
Next: Dijkstra’s Algorithm >>
More Code Examples Articles
More By Gabor Bernat
