Shortest Path Algorithms in Graphs - Dijkstra’s Algorithm
(Page 4 of 4 )
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
{
if (! queueD [p->value] && (distance [cur] + adiacentMatrix [cur] [p->value]) < distance [p->value])
{
ancient [p->value] = cur;
distance [p->value] = distance [cur] + adiacentMatrix [cur] [p->value];
}
}
}
printResult ();
}
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)).
-->Single Source Shortest Path Algorithms.zip<--
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!
| DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware. |
