The Bellman-Ford and Roy-Floyd Algorithms - The Bellman-Ford Algorithm
(Page 2 of 4 )
The Bellman-Ford technique continues the gradual approximation approach. If you missed my last article, I invite you to search it up and read it, as I will not explain again what is this all about and how it will help us in understanding and solving the problem.
While using the topological order-based approach and Dijkstra's Algorithm we found some ways to determine the right arrangement of the edges so that we may make the approximation when we need it. When a negative edge is also present in our graph, with circles whose sums remain positive, we can no longer find an order like this.
Therefore, we can no longer guarantee a single approximation with the edges. We will take the list of the edges and call the approximation algorithm as many times as an approximation is made. When we try to improve our distance array with each of the edges, and none can be made, we have finished the shortest path algorithm.
In the best-case scenario, this will lead to a single call. This is the case when all the edges are in the order they would be in the tree that builds the solution. This time, the solution is a tree whose root vertex is the source node from where we want to calculate the roads.
However, what is the limit of the maximal call, so that we do not enter into an endless loop? At the first call, the algorithm will solve the shortest path with the length of one edge. Further on, this will find the shortest roads containing two edges, and so on.
In the end, our tree must have n-1 edges, therefore executing the approximation through all edges n-1 times guarantees that we will get a good solution. If we do not know whether or not our input has negative circles, we can perform the approximation attempt once again on the graph (n-th time), and if it makes a single approximation, this will reveal a negative circuit.
The complexity is O (n*m), including the negative circuit fail-proof detection system. This will offer a result to any graph; however, this can turn out to be painfully slow.
The complexity of the topological order-based approach is O (n+m), and Dijkstra's Algorithm is O (m*lg (n)), so there is little competition if you want to solve a problem as fast as possible, and you know extra information, like the graph's contents include no circle or no negative edges. The parent-saving mechanism remains, so with a simple recursion we can print the roads as well. Here is the code snippet:
void BellmanFordAlgorithm (int root)
{
int i = 0;
int l;
int itwasMod = false;
for (i = 1; i <=n; ++i)
{
distance[i] = INT_MAX/2;
ancient[i] = 0;
}
distance [root] = 0;
ancient [root] = 0;
int k = 1;
do
{
itwasMod = false;
for (i = 1; i <= n; ++i)
{
for (l = 1; l <= n; ++l)
{
if (distance[i] + adiacentMatrix[i] [l] < distance[l]
&& distance[i] != INT_MAX/2
&& adiacentMatrix[i] [l] != INT_MAX/2) // Infinity plus/minus something is still infinity
{
ancient[l] = i;
itwasMod = true;
distance[l] = distance[i] + adiacentMatrix[i] [l];
}
}
}
} while (itwasMod && k<=n);
if (itwasMod)
printf ("Negative edge detected");
}
Next: The-Roy Floyd Technique >>
More Code Examples Articles
More By Gabor Bernat
