同义词Bellman-Ford算法（Bellman-Ford算法）一般指贝尔曼-福特算法
- 中文名
- 贝尔曼-福特算法
- 外文名
- Bellman-Ford
- 创立人
- 理查德·贝尔曼和莱斯特·福特
- 也被称为
- Moore-Bellman-Ford 算法
算法简介
播报编辑
贝尔曼-福特算法（英语旬府：Bellman–Ford algorithm），求解单源最短路径问题的催您狱项一种算法，由理查德·贝尔曼（Richard Bellman） 和莱斯特·福特创立的。有时候这种算法也被称为 Moore-Bellman雅辨-Ford 算法，因为Edward F. 桨台艰Moore也为这个算法的发展做出了贡献。它的原理是对图进行
贝尔曼-福特算法与迪科斯彻算法类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。在两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。 然而，迪科斯彻算法以贪心法选取未被处理的具有最小权值的节点，然后对其的出边进行松弛操作；而贝尔盼府船曼-福特算法简单地对所有边进行松弛操作，共
伪代码表示
播报编辑
procedure BellmanFord(list vertices, list edges, vertex source)
// 该实现读入边和节点的列表，并向两个数组（distance和predecessor）中写入最短路径信息
// 步骤1：初始化图
for each vertex v in vertices:
if v is source then distance[v] := 0
else distance[v] := infinity
predecessor[v] := null
// 步骤2：重复对每一条边进行松弛操作
for i from 1 to size(vertices)-1:
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
distance[v] := distance[u] + w
predecessor[v] := u
// 步骤3：检查负权环
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
error "图包含了负权环"
原理
播报编辑
松弛
每次松弛操作实际上是对相邻节点的访问，第
负边权操作
负权环判定
因为负权环可以无限制的降低总花费，所以如果发现第
优化
播报编辑
循环的提前跳出
在实际操作中，贝尔曼-福特算法经常会在未达到
队列优化
主条目：最短路径快速算法
西南交通大学的段凡丁于1994年提出了用队列来优化的算法。松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上，用一个队列记录松弛过的节点，可以避免了冗余计算。原文中提出该算法的复杂度为
Pascal语言示例
Begin
2 initialize-single-source(G,s);
3 initialize-queue(Q);
4 enqueue(Q,s);
5 while not empty(Q) do
6 begin
7 u:=dequeue(Q);
8 for each v∈adj[u] do
9 begin
10 tmp:=d[v];
11 relax(u,v);
12 if (tmp<>d[v]) and (not v in Q) then
13 enqueue(Q,v);
14 end;
15 end;
16 End;
C++语言示例
int SPFA(int s) {
2 queue<int> q;
3 bool inq[maxn] = {false};
4 for(int i = 1; i <= N; i++) dis[i] = 2147483647;
5 dis[s] = 0;
6 q.push(s); inq[s] = true;
7 while(!q.empty()) {
8 int x = q.front(); q.pop();
9 inq[x] = false;
10 for(int i = front[x]; i !=0 ; i = e[i].next) {
11 int k = e[i].v;
12 if(dis[k] > dis[x] + e[i].w) {
13 dis[k] = dis[x] + e[i].w;
14 if(!inq[k]) {
15 inq[k] = true;
16 q.push(k);
17 }
18 }
19 }
20 }
21 for(int i = 1; i <= N; i++) cout << dis[i] << ' ';
22 cout << endl;
23 return 0;
24 }
