Bellman-Ford algorithm

Sponsorship the way you would do it

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 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) 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.)

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