Bellman-Ford Algorithm

Bellman-Ford 算法用来求一个顶点到其他顶点的最短路径,可以处理权值为负数的有向图,但图中不能含有负权回路。

Bellman-Ford 算法基于一种松弛操作,在不断松弛的过程中,源点到其他每个点的路径值逐渐地得到优化,并最终达到最佳的答案。算法的实质就是反复地(重复|V|-1次)松弛所有的边,最后就可以计算出单源最短路。算法的时间复杂度是O(|V|*|E|),其中 |V| 和 |E| 分别是图的顶点数和边数。


function BellmanFord(list vertices, list edges, vertex source)
//(u,v)的权值 w

// Step 1: 对图进行初始化
for each vertex v in vertices:
if v is source then weight[v] := 0
else weight[v] := infinity
predecessor[v] := null

// Step 2: 不断松弛每条边,重复|V|-1次
for i from 1 to size(vertices)-1:
for each edge (u, v) with weight w in edges:
if weight[u] + w < weight[v]:
weight[v] := weight[u] + w
predecessor[v] := u

// Step 3: 检查是否有负权回路
for each edge (u, v) with weight w in edges:
if weight[u] + w < weight[v]:
error "Graph contains a negative-weight cycle"
return weight[], predecessor[]






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 from source to v with at most 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.

If there are no negative-weight cycles, then every shortest path visits each vertex at most once, so at step 3 no further improvements can be made. Conversely, suppose no improvement can be made. Then for any cycle with vertices v[0], …, v[k−1],

v[i].distance <= v[(i-1) mod k].distance + v[(i-1) mod k]v[i].weight

Summing around the cycle, the v[i].distance terms and the v[i−1 (mod k)] distance terms cancel, leaving

0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight

I.e., every cycle has nonnegative weight.


When the algorithm is used to find shortest paths, the existence of negative cycles is a problem, preventing the algorithm from finding a correct answer. However, since it terminates upon finding a negative cycle, the Bellman–Ford algorithm can be used for applications in which this is the target to be sought - for example in cycle-cancelling techniques in network flow analysis.


A distributed variant of the 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:

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 neighboring nodes.
When a node receives distance tables from its neighbors, it calculates the shortest routes to all other nodes and updates its own table to reflect any changes.
The main disadvantages of the Bellman–Ford algorithm in this setting are as follows:

It does not scale well.
Changes in network topology are not reflected quickly since updates are spread node-by-node.
Count to infinity (if link or node failures render a node unreachable from some set of other nodes, those nodes may spend forever gradually increasing their estimates of the distance to it, and in the meantime there may be routing loops).