The Bellman-Ford algorithm solves the single-source shortest-paths problem in the general case in which edge weights may be negative. Given a weighted, directed graph G = (V, E) with source s and weight function w : E → R, the Bellman-Ford algorithm returns a Boolean value indicating whether or not there is a negative-weight cycle that is reachable from the source. If there is such a cycle, the algorithm indicates that no solution exists. If there is no such cycle, the algorithm produces the shortest paths and their weights. The algorithm uses relaxation, progressively decreasing an estimate d[v] on the weight of a shortest path from the source s to each vertex v ∈ V until it achieves the actual shortest-path weight δ(s, v). The algorithm returns TRUE if and only if the graph contains no negative-weight cycles that are reachable from the source.
To understand this algorithm, we must know about the storing technique of graph.
The Algorithm
The Bellman-Ford algorithm is one of the classic solutions to this problem. It calculates the shortest path to all nodes in the graph from a single source.
The basic idea is simple:
Step 1: Start by considering that the shortest path to all nodes, less the source, is infinity. Mark the length of the path to the source as 0:
Step 2: Take every edge and try to relax it:
Relaxing an edge means checking to see if the path to the node the edge is pointing to can’t be shortened, and if so, doing it.
Now, we apply the previous step n – 1 times, where n is the number of nodes in the graph.
For example Click here
Here is the condensed form of the algorithm :
[code]
void bellman_ford(int s) {
int i, j;
for (i = 0; i < n; ++i)
d[i] = INFINITY;
d[s] = 0;
for (i = 0; i < n – 1; ++i)
for (j = 0; j < e; ++j)
if (d[edges[j].u] + edges[j].w < d[edges[j].v])
d[edges[j].v] = d[edges[j].u] + edges[j].w;
}
[/code]
***the structure is
[code]
typedef struct{
int u,v,w;
}Edge;
Edge edges[1000];
[/code]
It is seen that the working principle of Bellman-Ford algorithm is exactly same as another single source shortest path Dijkstra’s algorithm. Then what is the difference between them?
Yes, their working principle is same but Dijkstra’s algorithm fails if there exists any negative valued weight or negative cycle. But Bellman-Ford algorithm is capable to determine the negative cycle in the graph and finds the shortest path even with negative valued weights.
Here is an real life example of bellman-Ford example . UVA 558
[code]
//warmholes 558
#include <stdio.h>
typedef struct {
int u, v, w;
} Edge;
int n; /* the number of nodes */
int e; /* the number of edges */
Edge edges[2500]; /* large enough for n <= 2^5=32 */
int d[1500]; /* d[i] is the minimum distance from node s to node i */
#define INFINITY 1000000
void printDist() {
int i;
printf("Distances:n");
for (i = 0; i < n; ++i)
printf("to %dt", i );
printf("n");
for (i = 0; i < n; ++i)
printf("%dt", d[i]);
printf("nn");
}
void bellman_ford(int s){
int i, j;
for (i = 0; i < n; ++i)
d[i] = INFINITY;
d[s] = 0;
for (i = 0; i < n-1; ++i)
for (j = 0; j <e; ++j){
if (d[edges[j].u] + edges[j].w < d[edges[j].v])
d[edges[j].v] = d[edges[j].u] + edges[j].w;
}
////these 3 lines for the 558////////////////
int f=0;
for (int j = 0; j < e; j++)
if (d[edges[j].v] > d[edges[j].u] + edges[j].w) {
f=1;break;
}
if(f==1)
printf("possiblen");
else
printf("not possiblen");
}
int main() {
int i,p,j,k,c,l,m,kase;
int w;
scanf("%d",&kase);
for(c=0;c<kase;c++){
scanf("%d %d",&n,&e);
p=0;
for(i=0;i<e;i++){
scanf("%d %d %d",&j,&k,&l);
edges[i].u=j;
edges[i].v=k;
edges[i].w=l;
}
bellman_ford(0);
//printDist();
}
return 0;
}
[/code]
References:
“Introduction to algorithms ” by Coreman
http://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm/