Bellman-Ford algorithm
From Wikipedia, the free encyclopedia
Categories: Graph algorithms | Polynomial-time problems | Articles with example C code | Articles with example pseudocode
The Bellman–Ford algorithm, sometimes referred to as the Label Correcting Algorithm, computes single-source shortest paths in a weighted digraph (where some of the edge weights may be negative). Dijkstra's algorithm accomplishes the same problem with a lower running time, but requires edge weights to be non-negative. Thus, Bellman–Ford is usually used only when there are negative edge weights. According to Robert Sedgewick, "Negative weights are not merely a mathematical curiosity; [...] [they] arise in a natural way when we reduce other problems to shortest-paths problems,"[1] and he gives the specific example of a reduction from the NP-complete Hamilton-path problem. If a graph contains a cycle of total negative weight then arbitrarily low weights are achievable and so there's no solution; Bellman-Ford detects this case. Bellman-Ford is in its basic structure very similar to Dijkstra's algorithm, but instead of greedily selecting the minimum-weight node not yet processed to relax, it simply relaxes all the edges, and does this |V| − 1 times, where |V| is the number of vertices in the graph. The repetitions allow minimum distances to accurately propagate throughout the graph, since, in the absence of negative cycles, the shortest path can only visit each node at most once. Unlike the greedy approach, which depends on certain structural assumptions derived from positive weights, this straightforward approach extends to the general case. Bellman–Ford runs in O(V·E) time, where V and E are the number of vertices and edges respectively.
procedure 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)-1:
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"
Proof of correctnessThe correctness of the algorithm can be shown by induction. The precise statement shown by induction is: Lemma. After i repetitions of for cycle:
Proof. For the base case of induction, consider For the inductive case, we first prove the first part. Consider a moment when a vertex's distance is updated by 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 from source to v with at most i-1 edges. By inductive assumption, 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 walk, a shorter one exists, so there is no shortest walk. Otherwise, the shortest walk will not include any cycles (because going around a cycle would make the walk 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. Applications in routingA distributed variant of Bellman–Ford algorithm is used in distance-vector routing protocols, for example 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:
The main disadvantages of Bellman–Ford algorithm in this setting are
ImplementationThe following program implements the Bellman–Ford algorithm in C.
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
/* Let INFINITY be an integer value not likely to be
confused with a real weight, even a negative one. */
#define INFINITY ((1 << 14)-1)
typedef struct {
int source;
int dest;
int weight;
} Edge;
void BellmanFord(Edge edges[], int edgecount, int nodecount, int source)
{
int *distance = malloc(nodecount * sizeof *distance);
int i, j;
for (i=0; i < nodecount; ++i)
distance[i] = INFINITY;
distance[source] = 0;
for (i=0; i < nodecount; ++i) {
for (j=0; j < edgecount; ++j) {
if (distance[edges[j].source] != INFINITY) {
int new_distance = distance[edges[j].source] + edges[j].weight;
if (new_distance < distance[edges[j].dest])
distance[edges[j].dest] = new_distance;
}
}
}
for (i=0; i < edgecount; ++i) {
if (distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight) {
puts("Negative edge weight cycles detected!");
free(distance);
return;
}
}
for (i=0; i < nodecount; ++i) {
printf("The shortest distance between nodes %d and %d is %d\n",
source, i, distance[i]);
}
free(distance);
return;
}
int main(void)
{
/* This test case should produce the distances 2, 4, 7, -2, and 0. */
Edge edges[10] = {{0,1, 5}, {0,2, 8}, {0,3, -4}, {1,0, -2},
{2,1, -3}, {2,3, 9}, {3,1, 7}, {3,4, 2},
{4,0, 6}, {4,2, 7}};
BellmanFord(edges, 10, 5, 4);
return 0;
}
References
External linksde:Bellman-Ford-Algorithmus es:Algoritmo de Bellman-Ford fr:Algorithme de Ford-Bellman ko:벨만-포드 알고리즘 it:Algoritmo di Bellman-Ford he:אלגוריתם בלמן-פורד pl:Algorytm Bellmana-Forda pt:Algoritmo de Bellman-Ford ru:Алгоритм Беллмана — Форда vi:Thuật toán Bellman-Ford |
