The Bellman-Ford and Roy-Floyd Algorithms - Printing the road
(Page 4 of 4 )
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.
-->Shortest Path Algorithms.zip<--
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!
| 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. |
