Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于给定的带权（有向或无向）图
G=（V,E），其源点为s，加权函数
w是
边集 E
的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到
图G的任意顶点v的最短路径d[v]。
Bellman-Ford算法流程分为三个阶段：
（1）
初始化：将除源点外的所有顶点的最短距离估计值
d[v]
←+∞,
d[s] ←0;
（2）
迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）
（3）
检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在
d[v]中。
算法描述如下：
Bellman-Ford(G,w,s)
：boolean
//图G
，边集 函数
w ，s为源点
1
for each vertex v
∈
V（G）
do
//初始化 1阶段
2
d[v]
←+∞
3
d[s]
←0;
//1阶段结束
4
for i=1 to |v|-1
do
//2阶段开始，双重循环。
5
for
each edge（u,v）
∈E(G)
do //边集数组要用到，穷举每条边。
6
If
d[v]> d[u]+ w(u,v) then //松弛判断
7
d[v]=d[u]+w(u,v)
//松弛操作 2阶段结束
8
for each
edge（u,v）
∈E(G)
do
9
If
d[v]> d[u]+ w(u,v) then
10
Exit
false
11
Exit true
下面给出描述性证明：
首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|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
遍松弛操作仍然会成功，这时，负权回路上的顶点不会收敛。
改进和优化
如果循环n-1次以前已经发现不存在紧边则可以立即终止；
Yen氏改进（不降低渐进复杂度）；SPFA算法
二、
SPFA算法
算法简介
SPFA(Shortest
Path Faster Algorithm)是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。
它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。
算法流程
SPFA对Bellman-Ford算法优化的关键之处在于意识到：只有那些在前一遍松弛中改变了距离估计值的点，才可能引起他们的邻接点的距离估计值的改变。因此，算法大致流程是用一个队列来进行维护，即用一个先进先出的队列来存放被成功松弛的顶点。初始时，源点s入队。当队列不为空时，取出队首顶点，对它的邻接点进行松弛。如果某个邻接点松弛成功，且该邻接点不在队列中，则将其入队。经过有限次的松弛操作后，队列将为空，算法结束。SPFA算法的实现，需要用到一个先进先出的队列
queue
和一个指示顶点是否在队列中的标记数组mark。为了方便查找某个顶点的邻接点，图采用临界表存储。
算法代码
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;
负环处理
需要特别注意的是：仅当图不存在负权回路时，SPFA能正常工作。如果图存在负权回路，由于负权回路上的顶点无法收敛，总有顶点在入队和出队往返，队列无法为空，这种情况下SPFA无法正常结束。
判断负权回路的方案很多，世间流传最广、比较容易实现并且高效的方法的是记录每个结点进队次数，超过|V|次表示有负权
本题代码如下：Bellman-Ford算法实现
Code
#include<stdio.h>
#define MAX_INT 1000000
int t,n,m,s,e,nume;
int min[1002];
struct edge{
int s,e,c;
};
struct edge l[10002];
int process()
{
int i,j,k,flag,start,end;
for(i=0;i<n;i++)
min[i]=MAX_INT;
min[s]=0;
for(k=0;k<n-1;k++){
flag=0;
for(j=0;j<nume;j++){
start=l[j].s;
end=l[j].e;
if(min[end]>min[start]+l[j].c){
min[end]=min[start]+l[j].c;
flag=1;
}
}
if(!flag){
return 1;
}
}
for(j=0;j<nume;j++){
if(min[l[j].e]>min[l[j].s]+l[j].c)
return 0;
}
return 1;
}
void input()
{
int i,j,k,ii,flag;
scanf("%d %d",&n,&m);
nume=0;
while(m--){
scanf("%d %d %d",&i,&j,&k);
flag=0;
for(ii=0;ii<nume;ii++){
if(l[ii].s==i&&l[ii].e==e&&k<l[ii].c){
flag=1;
l[ii].c=k;
break;
}
}
if(!flag){
l[nume].s=i;l[nume].e=j;l[nume].c=k;nume++;}
}
scanf("%d %d",&s,&e);
}
int main()
{
scanf("%d",&t);
while(t--){
input();
if(min[e]==MAX_INT||!process())
printf("No\\n");
else
printf("%d\\n",min[e]);
}
}
|
题目练习：（转）
POJ
1201
Intervals
差分约束系统
设S(i)为
0..i-1
中在最终序列中的的整数个数。则约束条件如下:
S(b)-S(a)
>= c
0 <=
S(i+1) - S(i) <= 1 <==> S(i+1)-S(i) >= 0;
S(i)-S(i+1)
>= -1
注意本题要求的是最小值,
而按照>=号建图后发现图中有负环,
怎么办呢?
其实很简单,
本题求的不是最短路,
而是最长路!
Bellman_ford即可!
POJ
1275 Cashier Employment
出纳员的雇佣
黑书上有详细讲解
POJ
1364 King 差分约束系统
这个题目构图之后,
只需要用bellman_ford判断是否有负圈.
构图方法:
首先进行转换:a[j]+...+a[j+m]
= a[1]+...a[j+m] - (a[1]+...+a[j-1]) = sum[j+m] -
sum[j-1]
>(<) ki. 差分约束只能全部是<=或者(>=).
第二步转换:
sum[j+m]-sum[j-1] <= ki-1 或者
sum[j-1]-sum[j+m]
<= -ki-1.
约束图构造好后就是简单的Bellman-Ford了!
POJ
1716 Integer Intervals
是1201的简单版本,
贪心算法能够得到更好的效果.
POJ
2983 Is the Information Reliable?
差分约束题,
处理一下等号的情况,
然后普通的Bellman_ford
POJ
3159 Candies
最短路径
Bellman-Ford超时,
Dijkstra算法可以高效解决,
SPFA(队列)居然超时...SPFA修改为堆栈实现就过了.
POJ
3169 Layout
差分约束
Bellman-Ford
和 SPFA
实现均可
POJ
3259 Wormholes
判断负权回路
TOJ
2976 Path
单纯的最短路径
可练习SPFA
ZOJ
3033 Board Games 我做的第一道Bellman-Ford题目
code: