本文共 6275 字,大约阅读时间需要 20 分钟。
转自:
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算法能在更普遍的情况下(存在负权边)解决单源点最短路径问题。对于给定的带权(有向或无向)图 G=(V,E),其源点为s,加权函数 w是 边集 E 的映射。对图G运行Bellman-Ford算法的结果是一个布尔值,表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路,算法将给出从源点s到 图G的任意顶点v的最短路径d[v]。
(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) 来判断是否存在负权回路。
代码:
转自
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;};intmain(int argc, char **argv){ vector> Adj; int n, // 顶点数 m, //~ 边数 from, to, w, start; //~ 源点 cin>>n; vector Dist(n); for(int i = 0; i < n; ++i) { Adj.push_back(vector (n, MAXINT)); Adj[i][i] = 0; } cin>>m; vector 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!"< >to) { int rp = to; cout< <<" "; while(rp != start) //~ 反向输出路径 { cout<<<" <- "; if(Dist[to].w == MAXINT) break; rp = Dist[rp].src; } cout< <
转自:
一、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)。因为算法简单,适用范围又广,虽然复杂度稍高,仍不失为一个很实用的算法。
改进和优化 算法
二、 SPFA算法
算法简介
SPFA(Shortest Path Faster Algorithm)是的一种实现,减少了不必要的冗余计算。 它可以在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#include #include #define MAXV 10000#define INF 1000000000 //此处建议不要过大或过小,过大易导致运算时溢出,过小可能会被判定为真正的距离using std::vector;using std::queue;struct Edge{ int v; //边权 int to; //连接的点};vector e[MAXV]; //由于一般情况下E<
转载地址:http://sbeti.baihongyu.com/