中英▼

Bellman-Ford算法 百科内容来自于： 百度百科

算法介绍

Dijkstra算法无法判断含负权边的图的最短路。如果遇到负权，在没有负权回路存在时（负权回路的含义是，回路的权值和为负。）即便有负权的边，也可以采用Bellman-Ford算法正确求出最短路径，。
Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于给定的带权（有向或无向）图 G=（V,E），其源点为s，加权函数 w是 边集 E 的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到 图G的任意顶点v的最短路径d[v]。

适用条件&范围

1.单源最短路径(从源点s到其它所有顶点v);
2.有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);
3.边权可正可负(如有负权回路输出错误提示);
4.差分约束系统;

算法描述

1,.初始化：将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0;
2.迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）
3.检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 d[v]中。

描述性证明

首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。
其次，从源点s可达的所有顶点如果 存在最短路径，则这些最短路径构成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按顶点距离s的层次，逐层生成这棵最短路径树的过程。
在对每条边进行第1遍松弛的时候，生成了从s出发，层次至多为1的那些树枝。也就是说，找到了与s至多有1条边相联的那些顶点的最短路径；对每条边进行第2遍松弛的时候，生成了第2层次的树枝，就是说找到了经过2条边相连的那些顶点的最短路径……。因为最短路径最多只包含|v|-1 条边，所以，只需要循环|v|-1 次。
每实施一次松弛操作，最短路径树上就会有一层顶点达到其最短距离，此后这层顶点的最短距离值就会一直保持不变，不再受后续松弛操作的影响。（但是，每次还要判断松弛，这里浪费了大量的时间，怎么优化？单纯的优化是否可行？）
注意：上述只对正权图有效。如果存在负权不一定第i次就能确定最短路，且与边的顺序有关。
如果没有负权回路，由于最短路径树的高度最多只能是|v|-1，所以最多经过|v|-1遍松弛操作后，所有从s可达的顶点必将求出最短距离。如果 d[v]仍保持 +∞，则表明从s到v不可达。
如果有负权回路，那么第 |v| 遍松弛操作仍然会成功，这时，负权回路上的顶点不会收敛。

伪代码

PASCAL

For i:=1 to |V|-1 do
For 每条边(u,v)∈E do
Relax(u,v,w);
For每条边(u,v)∈E do
If dis[u]+w<dis[v] Then Exit(False)

C&C++

bool Bellman-Ford(G,w,s) //图G ，边集 函数 w ，s为源点
1 for each vertex v ∈ V（G） //初始化 1阶段
2 d[v] ←+∞;
3 d[s] ←0; //1阶段结束
4 for(int i=1;i<|v|;i++) //2阶段开始，双重循环。
5 for each edge（u,v） ∈E(G) //边集数组要用到，穷举每条边。
6 if(d[v]> d[u]+ w(u,v))//松弛判断
7 d[v]=d[u]+w(u,v); //松弛操作2阶段结束
8 for each edge（u,v） ∈E(G)
9 if(d[v]> d[u]+ w(u,v))
10 return false;
11 return true;

时空复杂度

算法时间复杂度O(VE)。因为算法简单，适用范围又广，虽然复杂度稍高，仍不失为一个很实用的算法。

参考代码

PASCAL

{单源最短路径的Bellman-ford算法
执行v-1次，每次对每条边进行松弛操作
如有负权回路则输出"Error"
}
const
maxn=100;
maxe=maxn*(maxn-1)div 2;
type
edge=record
a,b,w :integer;
end;
var
edges :array[1..maxe]of edge;
dis :array[1..maxn]of integer;
pre :array[1..maxn]of integer;
e,n,s :integer;
procedure init;
var
i :integer;
begin
e:=0;
assign(input,'g，in');reset(input);
readln(n,s);
while not eof do
begin
inc(e);
with edges[e] do readln(a,b,w);
end;
fillchar(dis,sizeof(dis),$7f);//$7f是什么，解释替换 $7f 是127 $在pascal中代表后面的数是16进制
dis[s]:=0;pre[s]:=s;
end;
procedure relax(u,v,w:integer);
begin
if dis[u]+w<dis[v] then
begin
dis[v]:=dis[u]+w;
pre[v]:=u;
end
end;
function bellman_ford:boolean;
var
i,j :integer;
begin
for i:=1 to n-1 do
for j:=1 to e do
with edges[j] do relax(a,b,w);
for i:=1 to e do
with edges[i] do
if dis[a]+w<dis[b] then exit(false);
exit(true)
end;
procedure print_path(i:integer);
begin
if pre[i]<>s then print_path(pre[i]);
write('-->',i)
end;
procedure show;
var
i :integer;
begin
for i:=1 to n do
begin
write(i:3,':',dis[i]:3,':',s);
print_path(i);
writeln
end;
end;
{========main========}
begin
init;
if bellman_ford then show
else writeln('Error!!')
end.

Matlab

function ford(d,n,s) % d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2...,n），s为源点标号
for i=1:n %初始化dist，pre
dist(i)=inf; %dist（i）为s，i之间的最短路的长度
pre(i)=NaN; %pre（i）为s到i的最短路上i的前一个顶点
end
dist(s)=0;
for k=1:n-1
for i=1:n %松弛操作
for j=1:n
if d(i,j)~=inf
if dist(j)>dist(i)+d(i,j)
dist(j)=dist(i)+d(i,j);
pre(j)=i;
end
end
end
end
end
for i=1:n
for j=1:n
if d(i,j)~=inf
if dist(i)+d(i,j)<dist(j)%判断有无负权回路
error('negetive weight circut');
end
end
end
end
dist
pre
end

C

int BellmanFord(int s,Wltem dist[],int prev[],Graph)
{
int i,j,k,n,*count,*ub;
queue qu;
glink p;
n=G->n;
if(s<1||s>n)
Error("Out of bounds");
count=malloc((n+1)*sizeof(int));
ub=malloc((n+1)*sizeof(int));
for(i=1;i<=n;i++)
{
dist[i]=INT_MAX;
count[i]=0;
prev[i]=0;
ub[i]=0;
}
qu=QueueInit();
dist[s]=0;
EnterQueue(s,qu);
while(!QueueEmpty(qu))
{
k=DeleteQueue(qu);
ub[k]=0;
count[k]++;
if(count[k]>n)
{
printf("cycle of negative weight exists!\n");
return 0;
}
p=G->adj[k];
while(p)
{
j=p->v;
if(dist[j]>dist[k]+p->w;
prev[j]=k;
if(!ub[j])
{
EnterQueue(j,qu);
ub[j]=1;
}
}
p=p->next;
}
}
return 1;
}

引申内容

SPFA算法
SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。

算法流程

算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束。

算法代码

Procedure SPFA;
Begin
initialize-single-source(G,s);
initialize-queue(Q);
enqueue(Q,s);
while not empty(Q) do begin
u:=dequeue(Q);
for each v∈adj[u] do begin
tmp:=d[v];
relax(u,v);
if (tmp<>d[v]) and (not v in Q) then enqueue(v);
end;
end;
End;

算法的优化

分析 Bellman-Ford算法，不难看出，外层循环（迭代次数）|v|-1实际上取得是上限。由上面对算法正确性的证明可知，需要的迭代遍数等于最短路径树的高度。如果不存在负权回路，平均情况下的最短路径树的高度应该远远小于 |v|-1，在此情况下，多余最短路径树高的迭代遍数就是时间上的浪费，由此，可以依次来实施优化。
从细节上分析，如果在某一遍迭代中，算法描述中第7行的松弛操作未执行，说明该遍迭代所有的边都没有被松弛。可以证明（怎么证明？）：至此后，边集中所有的边都不需要再被松弛，从而可以提前结束迭代过程。这样，优化的措施就非常简单了。
设定一个布尔型标志变量 relaxed，初值为false。在内层循环中，仅当有边被成功松弛时，将 relaxed 设置为true。如果没有边被松弛，则提前结束外层循环。这一改进可以极大的减少外层循环的迭代次数。优化后的 bellman-ford函数如下。
function bellmanford(s:longint):boolean;
begin
for i:=1 to nv do
d[i]:=max;
d[s]:=0;
for i:=1 to nv-1 do
begin
relaxed:=false;
for j:=1 TO ne do
if(d[edges[j].s]<>max) and (d[edges[j].e]>d[edges[j].s]+edges[j].w)
then begin
d[edges[j].e]:=d[edges[j].s]+edges[j].w ;
relaxed:=true;
end;
if not relaxed then break;
end;
for i:=1 to ne do
if d[edges[j].e]>d[edges[j].s]+edges[j].w then exit(false);
exit(true);
end;
这样看似平凡的优化，会有怎样的效果呢？有研究表明，对于随机生成数据的平均情况，时间复杂度的估算公式为
1.13|E| if |E|<|V|
0.95*|E|*lg|V| if |E|>|V|
优化后的算法在处理有负权回路的测试数据时，由于每次都会有边被松弛，所以relaxed每次都会被置为true，因而不可能提前终止外层循环。这对应了最坏情况，其时间复杂度仍旧为O(VE)。
优化后的算法的时间复杂度已经和用二叉堆优化的Dijkstra算法相近了，而编码的复杂程度远比后者低。加之Bellman-Ford算法能处理各种边值权情况下的最短路径问题，因而还是非常优秀的。
$firstVoiceSent
- 来自原声例句
小调查
请问您想要如何调整此模块？

感谢您的反馈，我们会尽快进行适当修改！
进来说说原因吧 确定
小调查
请问您想要如何调整此模块？

感谢您的反馈，我们会尽快进行适当修改！
进来说说原因吧 确定