Bellman-Ford algorithm computes single-source shortest paths in a weighted graph (where some of the edge weights may be negative). Dijkstra's algorithm accomplishes the same problem with a lower running time, but requires edges to be non-negative. Thus, Bellman-Ford is usually used only when there are negative edge weights.
Bellman Ford runs in O(VE) time, where V and E are the number of vertices and edges.
Here is a sample algorithm of Bellman-Ford
BF(G,w,s) // G = Graph, w = weight, s=source
Determine Single Source(G,s);
set Distance(s) = 0; Predecessor(s) = nil;
for each vertex v in G other than s,
set Distance(v) = infinity, Predecessor(v) = nil;
for i <- 1 to |V(G)| - 1 do //|V(G)| Number of vertices in the graph
for each edge (u,v) in G do
if Distance(v) > Distance(u) + w(u,v) then
set Distance(v) = Distance(u) + w(u,v), Predecessor(v) = u;
for each edge (u,r) in G do
if Distance(r) > Distance(u) + w(u,r);
return false; //This means that the graph contains a cycle of negative weight
//and the shortest paths are not well defined
return true; //Lengths of shortest paths are in Distance array
Proof of the Algorithm
The correctness of the algorithm can be shown by induction. The precise statement shown by induction is:
Lemma. After i repetitions of for cycle:
- If Distance(u) is not infinity, it is equal to the length of some path from s to u;
- If there is a path from s to u with at most i edges, then Distance(u) is at most the length of the shortest path from s to u with at most i edges.
Proof. For the base case of induction, consider i=0 and the moment before for cycle is executed for the first time. Then, for vertex s, Distance(s)=0 which is correct. For other vertices, Distance(u)=infinity which is also correct because there is no path from s to u with 0 edges.
For the inductive case, we first prove the first part. Consider a moment when Distance is updated by Distance(v) = Distance(u) + w(u,v) step. By inductive assumption, Distance(u) is the length of some path from s to u. Then, Distance(u) + w(u,v) is the length of the path from s to v that first goes from s to u and then from u to v.
For the second part, consider the shortest path from s to u with at most i edges. Let v be the last vertex before u on this path. Then, the part of the path from s to v is the shortest path between s to v with i-1 edges. By inductive assumption, Distance(v) after i-1 cycles is at most the length of this path. Therefore, Distance(v)+w(u,v) is at most the length of the path from s to u. In the ith cycle, Distance(u) gets compared with Distance(v)+w(u,v) and set equal to it, if Distance(v)+w(u,v) was smaller. Therefore, after i cycles Distance(u) is at most the length of the path from s to u.
End of proof.
The correctness of the algorithm follows from the lemma together with the observation that shortest path between any two vertices must contain at most V(G) edges. (If a path contained more than V(G) edges, it must contain some vertex v twice. Then, it can be shortened by removing the part between the first occurrence of v and the second occurrence. This means that it was not the shortest path.)
Implementations
#define INFINITY ((int) pow(2, sizeof(int)*8-2)-1)
typedef struct
{
int source;
int dest;
int weight;
}Edge;
void BellmanFord(Edge edges[], size_t edgecount, size_t nodecount, size_t source) // nodecount = number of vertices
{
int* distance = (int*) malloc(nodecount*sizeof(int));
for(int i = 0; i < nodecount; i++)
{
if(i == source) distance[i] = 0;
else distance[i] = INFINITY;
}
for(int i = 0; i < nodecount; i++)
{
for(int j = 0; j < edgecount; j++)
{
if(distance[edges[j].dest] > distance[edges[j].source] + edges[j].weight)
{
distance[edges[j].dest] = distance[edges[j].source] + edges[j].weight;
}
}
}
for(int i = 0; i < edgecount; i++)
{
if(distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight)
{
printf("Error occured. Negative edge weight cycles detected");
break;
}
}
for(int i = 0; i < nodecount; i++)
{
printf("The shortest distance between nodes %i and %i is %i", source, i, distance[i]);
}
}
Applications in routing
A distributed variant of Bellman-Ford algorithm is used in the Routing Information Protocol (RIP). The algorithm is distributed because it involves a number of nodes (routers) within an Autonomous system, a collection of IP networks typically owned by an ISP. It consists of the following steps:
- Each node calculates the distances between itself and all other nodes within the AS and stores this information as a table.
- Each node sends its table to all neighbouring nodes.
- When a node receives distance tables from its neighbours, it calculates the shortest routes to all other nodes and updates its own table to reflect any changes.
The main disadvantages of Bellman-Ford algorithm in this setting are
- Does not scale well
- Changes in network topology are not reflected quickly since updates are spread node-by-node.
- Counting to infinity
See also: List of algorithms