Shortest Path Algorithms in Graphs - The gradual approximation
(Page 2 of 4 )
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.
Next: The Topological Order-Based Algorithm >>
More Code Examples Articles
More By Gabor Bernat
