转自：http://hi.baidu.com/jzlikewei/blog/item/94db7950f96f995a1038c2cd.html
Bellman-Ford算法与另一个非常著名的Dijkstra算法一样，用于求解单源点最短路径问题。Bellman-ford算法除了可求解边权均非负的问题外，还可以解决存在负权边的问题（意义是什么，好好思考），而Dijkstra算法只能处理边权非负的问题，因此 Bellman-Ford算法的适用面要广泛一些。但是，原始的Bellman-Ford算法时间复杂度为 O（VE）,比Dijkstra算法的时间复杂度高，所以常常被众多的大学算法教科书所忽略，就连经典的《算法导论》也只介绍了基本的Bellman-Ford算法，在国内常见的基本信息学奥赛教材中也均未提及，因此该算法的知名度与被掌握度都不如Dijkstra算法。事实上，有多种形式的Bellman-Ford算法的优化实现。这些优化实现在时间效率上得到相当提升，例如近一两年被热捧的SPFA（Shortest-Path
Faster Algoithm 更快的最短路径算法）算法的时间效率甚至由于Dijkstra算法，因此成为信息学奥赛选手经常讨论的话题。然而，限于资料匮乏，有关Bellman-Ford算法的诸多问题常常困扰奥赛选手。如：该算法值得掌握么？怎样用编程语言具体实现？有哪些优化？与SPFA算法有关系么？本文试图对Bellman-Ford算法做一个比较全面的介绍。给出几种实现程序，从理论和实测两方面分析他们的时间复杂度，供大家在备战省选和后续的noi时参考。
Bellman-Ford算法思想
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 遍松弛操作仍然会成功，这时，负权回路上的顶点不会收敛。
例如对于上图，边上方框中的数字代表权值，顶点A,B,C之间存在负权回路。S是源点，顶点中数字表示运行Bellman-Ford算法后各点的最短距离估计值。
此时d[a]的值为1，大于d[c]+w(c,a)的值-2，由此d[a]可以松弛为-2，然后d[b]又可以松弛为-5,d[c]又可以松弛为-7.下一个周期，d[a]又可以更新为更小的值，这个过程永远不会终止。因此，在迭代求解最短路径阶段结束后，可以通过检验边集E的每条边(u,v)是否满足关系式d[v]> d[u]+ w(u,v) 来判断是否存在负权回路。
代码：
转自http://www.dutor.net/index.php/2010/05/shortest-path-bellman-ford/
const int MAXINT = 0xFFFF; //~ 不可达的路径长度上限
struct Node
{
Node(): w(MAXINT){}
int src, //~ 最短路径上的上一个顶点
w; //~ 到该节点的路径长度
};
struct Edge
{
Edge(){}
Edge(int f, int t): from(f), to(t){}
int from,
to;
};
int
main(int argc, char **argv)
{
vector<vector<int> > Adj;
int n, // 顶点数
m, //~ 边数
from,
to,
w,
start; //~ 源点
cin>>n;
vector<Node> Dist(n);
for(int i = 0; i < n; ++i)
{
Adj.push_back(vector<int>(n, MAXINT));
Adj[i][i] = 0;
}
cin>>m;
vector<Edge> Edges;
for(int i = 0; i < m; ++i)
{
cin>>from>>to>>w;
Adj[from][to] = w;
Edges.push_back(Edge(from, to));
}
cin>>start; //~ 从顶点start开始的最短路径
Dist[start].w = 0; //~
bool flag = true;
for( int i = 0; i < n - 1; ++i)
{
for(int j = 0; j < Edges.size(); ++j)
{
from = Edges[j].from;
to = Edges[j].to;
if(Dist[from].w == MAXINT || Adj[from][to] == MAXINT)
continue;
if(Dist[from].w + Adj[from][to] < Dist[to].w)
{
Dist[to].w = Dist[from].w + Adj[from][to];
Dist[to].src = from;
flag = false;
}
}
if(flag == true)
break;
else
flag = true;
}
//~ 检测有无负环路
for(int j = 0; j < Edges.size(); ++j)
{
from = Edges[j].from;
to = Edges[j].to;
if(Dist[from].w == MAXINT || Adj[from][to] == MAXINT)
continue;
if(Dist[from].w + Adj[from][to] < Dist[to].w)
{
cout<<"Negative Length Cycle Detected!"<<endl;
return 1;
}
}
//~ 下面代码供测试用
while(cin>>to)
{
int rp = to;
cout<<Dist[to].w<<" ";
while(rp != start) //~ 反向输出路径
{
cout<<rp<<" <- ";
if(Dist[to].w == MAXINT) break;
rp = Dist[rp].src;
}
cout<<start<<endl;
}
return 0;
}
转自：http://blog.csdn.net/xiaofengsheng/article/details/3717194
一、Bellman-Ford算法
最优性原理
它是最优性原理的直接应用，算法基于以下事实：
l 如果最短路存在，则每个顶点最多经过一次，因此不超过n-1条边；
l 长度为k的路由长度为k-1的路加一条边得到；
l 由最优性原理，只需依次考虑长度为1，2，…，k-1的最短路。
l 单源最短路径(从源点s到其它所有顶点v);
l 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);
l 边权可正可负(如有负权回路输出错误提示);
l 差分约束系统（需要首先构造约束图，构造不等式时>=表示求最小值, 作为最长路，<=表示求最大值, 作为最短路。<=构图时, 有负环说明无解；求不出最短路（为Inf）为任意解。>=构图时类似）。
算法描述
l 对每条边进行|V|-1次Relax操作;
l 如果存在(u,v)∈E使得dis[u]+w<dis[v],则存在负权回路;否则dis[v]即为s到v的最短距离,pre[v]为前驱。
时空复杂度
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)
算法时间复杂度O(VE)。因为算法简单，适用范围又广，虽然复杂度稍高，仍不失为一个很实用的算法。
改进和优化 如果循环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;
#include<cstdio>
#include<vector>
#include<queue>
#define MAXV 10000
#define INF 1000000000 //此处建议不要过大或过小,过大易导致运算时溢出,过小可能会被判定为真正的距离
using std::vector;
using std::queue;
struct Edge{
int v; //边权
int to; //连接的点
};
vector<Edge> e[MAXV]; //由于一般情况下E<<V*V,故在此选用了vector动态数组存储,也可以使用链表存储
int dist[MAXV]; //存储到原点0的距离,可以开二维数组存储每对节点之间的距离
int cnt[MAXV]; //记录入队次数,超过V则退出
queue<int> buff; //队列,用于存储在SPFA算法中的需要松弛的节点
bool done[MAXV]; //用于判断该节点是否已经在队列中
int V; //节点数
int E; //边数
bool spfa(const int st)
{ //返回值:TRUE为找到最短路返回,FALSE表示出现负环退出
for(int i=0;i<V;i++)
{ //初始化:将除了原点st的距离外的所有点到st的距离均赋上一个极大值
if(i==st)
{
dist[st]=0; //原点距离为0;
continue;
}
dist[i]=INF; //非原点距离无穷大
}
buff.push(st); //原点入队
done[st]=1; //标记原点已经入队
cnt[st]=1; //修改入队次数为1
while(!buff.empty())
{ //队列非空,需要继续松弛
int tmp=buff.front(); //取出队首元素
for(int i=0;i<(int)e[tmp].size();i++)
{ //枚举该点连接的每一条边
Edge *t=&e[tmp][i]; //由于vector的寻址速度较慢,故在此进行一次优化
if(dist[tmp]+(*t).v<dist[(*t).to])
{ //更改后距离更短,进行松弛操作
dist[(*t).to]=dist[tmp]+(*t).v; //更改边权值
if(!done[(*t).to])
{ //没有入队,则将其入队
buff.push((*t).to); //将节点压入队列
done[(*t).to]=1; //标记节点已经入队
cnt[(*t).to]=1; //节点入队次数自增
if(cnt[(*t).to]>V)
{ //已经超过V次,出现负环
while(!buff.empty())buff.pop(); //清空队列,释放内存
return false; //返回FALSE
}
}
}
}
buff.pop();//弹出队首节点
done[tmp]=0;//将队首节点标记为未入队
}
return true; //返回TRUE
} //算法结束
int main()
{ //主函数
scanf("%d%d",&V,&E); //读入点数和边数
for(int i=0,x,y,l;i<E;i++)
{
scanf("%d%d%d",&x,&y,&l); //读入x,y,l表示从x->y有一条有向边长度为l
Edge tmp; //设置一个临时变量,以便存入vector
tmp.v=l; //设置边权
tmp.to=y; //设置连接节点
e[x].push_back(tmp); //将这条边压入x的表中
}
if(!spfa(0))
{ //出现负环
printf("出现负环,最短路不存在\n");
}else
{ //存在最短路
printf("节点0到节点%d的最短距离为%d",V-1,dist[V-1]);
}
return 0;
}