Bellman-ford算法是求含负权图的单源最短路径算法，效率很低，但代码很容易写。即进行不停地松弛（原文是这么写的，为什么要叫松弛，争议很大），每次松弛把每条边都更新一下，若n-1次松弛后还能更新，则说明图中有负环，无法得出结果，否则就成功完成。Bellman-ford算法有一个小优化：每次松弛先设一个旗帜flag，初值为FALSE，若有边更新则赋值为TRUE，最终如果还是FALSE则直接成功退出。Bellman-ford算法浪费了许多时间做无必要的松弛，所以SPFA算法用队列进行了优化，效果十分显著，高效难以想象。SPFA还有SLF，LLL，滚动数组等优化。

<Bellman-Ford算法>

引申：SPFA算法

算法流程

<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.差分约束系统;

Bellman-Ford算法描述：

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 次。

每实施一次松弛操作，最短路径树上就会有一层顶点达到其最短距离，此后这层顶点的最短距离值就会一直保持不变，不再受后续松弛操作的影响。（但是，每次还要判断松弛，这里浪费了大量的时间，怎么优化？单纯的优化是否可行？）

如果没有负权回路，由于最短路径树的高度最多只能是|v|-1，所以最多经过|v|-1遍松弛操作后，所有从s可达的顶点必将求出最短距离。如果 d[v]仍保持 +∞，则表明从s到v不可达。

如果有负权回路，那么第 |v|-1 遍松弛操作仍然会成功，这时，负权回路上的顶点不会收敛。

伪代码

-------------------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

引申：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;