//参数：所有点的集合，所有边的集合，源点 functionBellmanFord(listvertices, listedges, vertexsource) //需要的变量： //（u，v）的权值 w //数组weight，源点到每个顶点的最短路 //数组predecessor，在最短路中，每个顶点的前继
// Step 1: 对图进行初始化 foreach 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 from1to size(vertices)-1: //下面松弛每一条边，可以使用二重循环处理 foreach edge (u, v) with weight w in edges: if weight[u] + w < weight[v]: weight[v] := weight[u] + w predecessor[v] := u
// Step 3: 检查是否有负权回路 foreach 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, …, 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).