• • • • • • • •
• • • •
function bellman(v:longint):boolean; var i,j,k:longint; begin for i:=1 to n do d[i]:=wq; {顶点v到各顶点的初值为正无穷} d[v]:=0; for i:=1 to n do for j:=1 to ne do {存储结构用边集数组，ne表示边的个数} if (d[edge[j].st]<>wq) and (d[edge[j].en]>d[edge[j].st]+edge[j].w) then d[edge[j].en]:=d[edge[j].st]+edge[j].w); for j:=1 to ne do if (d[edge[j].en]>d[edge[j].st]+edge[j].w) then exit(false); bellman:=true; end;
Floyd算法——解决多源最短路径问题
• 该算法使用了动态规划的思想，首先，将图中顶点编 号为1——n,以两点之间最短路径经过的顶点中最大 的顶点编号作为阶段，而两点间目前算出的最短路径 作为状态的值。 • 设F[i,j,k]为顶点编号为i和j两点经过最大顶点编号 不超过k的最短路径的长度，那么，
DIJKSTRA算法——单源最短路径算法
• • • • • • • • • • • • • • • • • • • • • • procedure shortpath(v:integer); var wm:integer; begin for i:=1 to n do begin dist[i]:=g[v,i]; if dist[i]<max1 then path[i]:=[v]+[i] else path[i]:=[]; end; s:=[v]; for k:=1 to n-1 do begin wm:=max1; j:=v; for i:=1 to n do if not (i in s) and (dist[i]<wm) then begin j:=i; wm:=dist[i] end; s:=s+[j]; for i:=1 to n do if not (i in s) and (dist[j]+g[j,i]<dist[i]) then begin dist[i]:=dist[j]+g[j,i]; path[i]:=path[j]+[i] end end; end;
Floyd算法——解决多源最短路径问题
• 算法本质：通过某个点，是否可以使两个点的距离变短， 而不是两个点之间的距离是否可以通过某个点变短，所以 最外成的循环（相当于动态规划的阶段）不能和里面的两 层循环顺序颠倒。 • 空间复杂度O(n^2),时间复杂度O(n^3)。
DIJKSTRA算法——单源最短路径算法 Node
New
Head
Tail
缺点：NewNode需要之前的元素全部出队后才能扩展 中断了迭代的连续性
猜想： 能否把NewNode放在Head后面进行下一次扩展？
小结
Dijkstra算法的效率高，但是也有局限性，就是对于含负权回路 的图无能为力。 Bellman-Ford算法对于所有最短路存在的图都适用，但是效率常常 不尽人意。 SPFA算法可以说是综合了上述两者的优点。它的效率同样很不错， 而且对于最短路长存在的图都适用，无论是否存在负权。它的编程 复杂度也很低，是高性价比的算法。
注意：
• 当图中不存在负权回路时，程序能正常工作；如果存在负 权回路，由于负权回路上的顶点无法收敛，总有顶点在入 队和出队中往返，队列无法为空，这种情况下SPFA无法正 常结束。 • 处理方法：增加一个一维数组times来统计每个顶点进栈 的次数，如果times[i]>n，说明存在负权回路。
传统的队列实现:
• 每实施一次松弛操作，最短路径树上就会有一层顶点达到 其最短距离，此后这层顶点的最短距离值就会保持不变， 不再受后续松弛操作的影响。 • 如果没有负权回路，由于最短路径的高度最多是V-1，所 以最多经过V-1遍松弛操作后，所有从s可达的顶点必将求 出其最短距离。如果d[v]仍保持+∞，则表明从s到v不可 达。 • 如果有负权回路，那么第V-1遍松弛操作仍然会成功，这 时，负权回路上的顶点不会收敛。
Dijkstra算法
适用条件: 所有边的权值非负 效率:
用一维数组来实现优先队列Q，O( V 2 )，适用于中等规模 的稠密图
二叉堆来实现优先队列Q，O((E+logV)V)，适用于稀疏图
Bellman-Ford算法
Bellman-Ford算法运用了松弛技术，对 每一结点V，逐步减小从源s到v的最短路径的 估计值d[v]直至其达到实际最短路径的权 d(s,v)，如果图中存在负权回路，算法将会报 告最短路不存在;若不存在这样的回路，算法 将给出从源点S到图G的任意顶点v的最短路 径值d[v]。
算法流程
• (1)初始化：将除源点外的所有顶点的最短距离估计值 d[v]:=+∞； d[s]:=0; • (2)迭代求解：反复对边集E中的每条边进行松弛操作，使 得顶点V集中的每个顶点v的最短距离估计值逐步逼近其最 短距离； • (3)检验负权回路：判断边集E中的每一条边的两个端点是 否收敛。如果存在未收敛的顶点，则算法返回false，表 明问题无解；否则算法返回true，并且从源点可达的顶点 v的最短距离保存在d[v]中。
SPFA算法
适用条件: 任意边权为实数的图
定理3 只要最短路径存在，上述SPFA算法必定能求出最小值。 证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的 优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d 越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短 路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到 达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最 短路径值。（证毕） 定理4 在平均情况下，SPFA算法的期望时间复杂度为O(E)。 证明：上述算法每次取出队首结点u，并访问u的所有临结点的复杂度 为O(d)，其中d为点u的出度。运用均摊分析的思想，对于|V|个点|E|条 E E 边的图，点的平均出度为 V，所以每处理一个点的复杂度为O(V )。假 设结点入队次数为h，显然h随图的不同而不同。但它仅与边权值分布 E h T O h O E O(kE ) 有关。我们设h=kV，则算法SPFA的时间复杂度为 V V 在平均的情况下，可以将k看成一个比较小的常数，所以SPFA算法在 一般情况下的时间复杂度为O(E)。（证毕）
算法证明
• 首先，图的任意一条最短路径既不能包含负权回路，也不 会包含正权回路，因此它最多包含V-1条边。 • 其次，从源点s可达的所有顶点如果存在最短路径，则这 些最短路径构成一个以s为根的最短路径树。BellmanFord算法的迭代松弛操作，实际上就是按顶点距离s的层 次，逐层生成这棵最短路径树的过程。 • 在对每条边进行第1遍松弛的时候，生成了从s出发，层次 至多为1的那些树枝。也就是说，找到了与s至多有1条边 相连的那些顶点的最短路径；在对每条边进行第2遍松弛 的时候，生成了从s出发，层次至多为2的那些树枝……
SPFA(shortest path faster algorithm)
• 在Bellman-ford算法优化的基础上发现，只有那些在前一 遍松弛中改变了距离估计值的点，才可能引起它们的邻接 点的距离估计值的改变。 • 因此，用一个先进先出的队列来存放被成功松弛的顶点。 初始时，源点s入队。当队列不空时，取出队首顶点，对 它的邻接点进行松弛。如果某个邻接点松弛成功，且该邻 接点不在队列中，则将其入队。经过有限次的松弛操作后 ，队列为空，算法结束。 • 算法的实现需要用一个先进先出的队列queue和一个指示 顶点是否在队列中的标记数组mark。为了方便查找某个顶 点的邻接点，图采用邻接表存储。
Bellman-Ford算法
适用条件: 任意边权为实数的图 效率: Bellman-Ford算法的运行时间为O(VE)。很多时候， 我们的算法并不需要运行|V|-1次就能得到最优值。 对于一次完整的松弛操作，要是一个结点的最短路 径估计值也没能更新，就可以退出了。 经过优化后，对于多数情况而言，程序的实际运行效 率将远离O(VE)而变为O(kE)，其中k是一个比|V|小很 多的数。
• 该算法基于一种贪心思想，主要用到松弛操作。 • 对一条边进行松弛操作时，考查该边的起点S和终点T，权 值W是否满足如下不等式： • DS+W<DT • 如果该边满足不等式，那么以源点到S的最短路径加上这 一条边会使得源点到点T的最短路径比目前的值更小，此 时，更新源点到点T的最短路径。 • 算法思想:每次找到源点最短路径最短的一个顶点，然后 以该顶点为中心进行扩展，最终得到给定源点到所有其余 顶点的最短路径。
• • • • • • • • • • • • • • for i:=1 to n do //初始化 for j:=1 to n do if i<>j then d[i,j]:=maxlongint else d[i,j]:=0; for i:=1 to m do //读入边的权值 begin readln(u,v,w); d[u,v]:=w; end; for k:=1 to n do for i:=1 to n do for j:=1 to n do if d[i,k]+d[k,j]<d[i,j] then d[i,j]:=d[i,k]+d[k,j];
算法框架
Bellman-Ford(G,w,s) 1. For each vertex v∈ V[G] do //初始化 2. d[v]:=+ ∞; 3. d[s]:=0; 4. For i ← 1 to |V[G]|-1 do 5. For 每条边(u,v) ∈ E[G] do 6. If d[v] > d[u] + w(u, v) then d[v] := d[u] + w(u, v) 7. For 每条边(u,v) ∈ E[G] do 8. If d[v] > d[u] + w(u, v) //检查负权回路 9. Then Return FALSE 10. Return TRUE