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.
// Define datatypes for a graph
record vertex {
list edges
real distance
vertex predecessor
}
record edge {
node source
node dest
real weight
}
function BellmanFord(list vertices, list edges, vertex source)
// This implementation takes in a graph, represented as lists of vertices
// and edges, and modifies the vertices so that their distance and
// predecessor attributes store the shortest paths.
// Step 1: Initialize graph
for each vertex v in vertices:
if v is source then v.distance = 0
else v.distance = infinity
v.predecessor = null
// Step 2: relax edges repeatedly
for i from 1 to size(vertices):
for each edge uv in edges:
u := uv.source
v := uv.destination // uv is the edge from u to v
if v.distance > u.distance + uv.weight
v.distance := u.distance + uv.weight
v.predecessor := u
// Step 3: check for negative-weight cycles
for each edge uv in edges:
u := uv.source
v := uv.destination
if v.distance > u.distance + uv.weight
error "Graph contains a negative-weight cycle"
| Contents |
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 the source vertex, source.distance = 0, which is correct. For other vertices u, u.distance = infinity, which is also correct because there is no path from source to u with 0 edges.
For the inductive case, we first prove the first part. Consider a moment when a vertex's distance is updated by
v.distance := u.distance + uv.weight. By inductive assumption, u.distance is the length of some path from source to u. Then u.distance + uv.weight is the length of the path from source to v that follows the path from source to u and then goes to v.
For the second part, consider the shortest path from source 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 source to v is the shortest path between source to v with i-1 edges. By inductive assumption, v.distance after i-1 cycles is at most the length of this path. Therefore, uv.weight + v.distance is at most the length of the path from s to u. In the ith cycle, u.distance gets compared with uv.weight + v.distance, and is set equal to it if uv.weight + v.distance was smaller. Therefore, after i cycles, u.distance is at most the length of the shortest path from source to u that uses at most i edges.
When i equals the number of vertices in the graph, each path will be the shortest path overall, unless there are negative-weight cycles. If a negative-weight cycle exists and is accessible from the source, then given any path, a shorter one exists, so there is no shortest path. Otherwise, the shortest path will not include any cycles (because going around a cycle would not make the path shorter), so each shortest path visits each vertex at most once, and its number of edges is less than the number of vertices in the graph. Therefore, each path stored in the graph by this point is the shortest path.
End of proof.
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
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 i,j ;
int* distance = (int*) malloc(nodecount*sizeof(int));
for(i = 0; i < nodecount; i++)
{
if(i == source) distance[i] = 0;
else distance[i] = INFINITY;
}
for(i = 0; i < nodecount; i++)
{
for(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(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(i = 0; i < nodecount; i++)
{
printf("The shortest distance between nodes %i and %i is %i", source, i, distance[i]);
}
}
References
- Richard Bellman: On a Routing Problem, in Quarterly of Applied Mathematics, 16(1), pp.87-90, 1958.
- Lestor R. Ford jr., D. R. Fulkerson: Flows in Networks, Princeton University Press, 1962.
See also
fr:Algorithme de Ford-Bellman he:אלגוריתם בלמן-פורד pt:Algoritmo de Bellman-Ford zh:Bellman-Ford算法