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;
return true;
Proof of the Algorithm
- TODO
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