Bellman–Ford algorithm

The 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 correctness

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 i^th 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)-1 edges. (If a path contained more than V(G)-1 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

C

#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)
{
	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 occurred. 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