The Bellman-Ford and Roy-Floyd Algorithms - The-Roy Floyd Technique
(Page 3 of 4 )
The previous algorithm's goal was to determine the shortest path from a source vertex to all the other vertexes. Now we are going to calculate the shortest paths between all the nodes inside a graph. The technique, also variously known as Floyd's algorithm, the Roy-Warshall algorithm, the Roy-Warshall algorithm, or the WFI algorithm is an extension of the Bellman Ford algorithm to the whole graph and all the vertexes.
The only prerequisite of this algorithm remains that the graph should not contain any negative circuits. You can perceive the algorithm as similar to the earlier approach, but now we are going to build n trees simultaneously, and each one of them will contain in the end the shortest path from a vertex to all the others.
We will switch our array of distances to two-dimensional arrays that at the start will be the same as the weight matrix. Therefore, we will guesstimate that the shortest road between two vertexes is the edge connecting them if it exists, infinity if there are no edges connecting and zero between the same vertexes.
This is the initial start of the matrix. Now on this matrix we are going to make the approach n times, which is similar to how we made it with of Bellman-Ford. At step k, we are going to build the distance matrix from the k-1 state. Starting from the simple, trivial solution, we are going to create a more complex solution.
This method is well known under the name of the dynamic programming technique. At each step, we will check if the "k" vertex is on the shortest road between "i" and "j". If the answer is yes, we do not need to make any further approximations; otherwise, we will make this part of the road by adding the current known shortest road between "i"-"k" and "k"-"j".
This is true because the shortest road is built from the sub-shortest roads. In addition, if we know the shortest road between edges "i"-"k" and "k"-"j" then we can conclude that "i"-"j" is the shortest road between node "i" and "j".
We need to repeat this n times, and the solution is complete. At each step, at least one shortest road will be determined, so at the end of n steps, all of the graph's shortest roads should be calculated.
The complexity of all this, due to the fact that we make n iterations on the distance matrix, which is also of a size n X n, will be O (n^3). This is quite bad, so unless you need all of the roads and shortest paths, avoid using it. We can determine whether we have negative circles in the graph in two ways.
We can observe that if, on the main diagonal after the n iteration, we can find a negative number (meaning that there is a road between "i" and "i" less than zero), we have a negative circle. Or, as in the case of the Bellman-Ford algorithm, we can run the approximation approach again and observe whether or not another change is made. The code snippet should look like this:
void RoyFloyd ()
{
int i =0;
int j = 0;
int k = 0;
// initialize the priorAncient array
// Assign the default distances we estimate
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
{
if (weightMatrix[i] [j] == INFINITY || i == j)
priorAncientV[i] [j] = 0;
else
priorAncientV[i] [j] = i;
distance[i] [j] = weightMatrix[i] [j];
}
for (k = 1; k <= n; ++k)
{
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (i!=k && j!=k)
if (distance[i] [k] + distance[k][j] < distance[i][j] && distance[i] [k] != INFINITY
&& distance[k] [j]!= INFINITY)
// INFINITY plus/minus something is still infinity
{
// make the approximation
distance[i] [j] = distance[i][k] + distance[k][j];
priorAncientV[i] [j] = priorAncientV[k] [j];
}
}
}
Next: Printing the road >>
More Code Examples Articles
More By Gabor Bernat
