最短路算法总结

西北狼666

1.floyd算法 （n^3复杂度）
6 \) ]+ Z% ?7 C, R基本思想：开始设集合S的初始状态为空，然后依次将0,1，。。n-1定点加入，同时用d[j]保存从i到j，仅经过S中的定点的最短路径，在初始时刻，d[j]= A[j]中间不经过任何节点，然后依次向S中插入节点，并进行如下更新
d(k)[j] = min{ d(k-1)[j],d(k-1)[k]+d(k-1)[k][j]}
# j3 q. a2 a! Z2 I7 m- ]还可以使用一个二维数组path指示最短路径。
5 s# f% N2 M5 Gpath[j]给出从定点i到j的最短路径上，定点i的前一个顶点
代码相当简单，最容易的实现方法：

[cpp] view plain copy

1. for (k = 0;k < n;k++)  

2. for (i = 0;i < n;i++)  

3. for (j = 0;j < n;j++)  

4. {  

5.     if (d[k] + d[k][j] < d[j])  

6.     {  

7.         d[j] = d[k] + d[k][j];  

8.         path[j] = path[k][j];  

9.     }  

10.}  

3 [; I; c3 p; [+ ~- Q

5 I# m# k/ u. d5 A, T然后可以通过递归得出路径的。。

2.dijstra算法

单源最短路问题，先加入源，维持一张表来保存此时到源中的最短距离，选取最小的加入，然后更新表，不断的加入直到目的地在源中。仅适用于正边权的时侯，因为这时我们可以保证任意加入的点已经找到了源到该点的距离。

3.bellman-ford算法

最优性原理

最优性原理介绍及简单证明见：http://blog.csdn.net/liguanxing/article/details/7401798

它是最优性原理的直接应用，算法基于以下事实：

如果最短路存在，则每个顶点最多经过一次，因此不超过n-1条边；

长度为k的路由长度为k-1的路加一条边得到；

由最优性原理，只需依次考虑长度为1，2，…，k-1的最短路。

适用条件&范围

单源最短路径(从源点s到其它所有顶点v);

有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);

边权可正可负(如有负权回路输出错误提示);

差分约束系统（需要首先构造约束图，构造不等式时>=表示求最小值,作为最长路，<=表示求最大值,作为最短路。<=构图时,有负环说明无解；求不出最短路（为Inf）为任意解。>=构图时类似）。  

算法描述

1）对每条边进行|V|-1次Relax操作;

2）如果存在(u,v)∈E使得dis+w<dis[v],则存在负权回路;否则dis[v]即为s到v的最短距离,pre[v]为前驱。  

[c-sharp] view plain copy

1. for i:=1 to |V|-1 do //进行|v|-1次松弛得最短距离  

2.     for 每条边(u,v)∈E do     

3.         Relax(u,v,w);  

4. for每条边(u,v)∈E do //判断是否存在负权环  

5.     if dis+w<dis[v]   

6.         Then Exit(False)  

算法时间复杂度O(VE)。因为算法简单，适用范围又广，虽然复杂度稍高，仍不失为一个很实用的算法。  

改进和优化  如果循环n-1次以前已经发现不存在紧边则可以立即终止；

4.spfa算法

SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。

算法流程  

SPFA对Bellman-Ford算法优化的关键之处在于意识到：只有那些在前一遍松弛中改变了距离估计值的点，才可能引起他们的邻接点的距离估计值的改变。因此，算法大致流程是用一个队列来进行维护，即用一个先进先出的队列来存放被成功松弛的顶点。初始时，源点s入队。当队列不为空时，取出队首顶点，对它的邻接点进行松弛。如果某个邻接点松弛成功，且该邻接点不在队列中，则将其入队。经过有限次的松弛操作后，队列将为空，算法结束。SPFA算法的实现，需要用到一个先进先出的队列 queue 和一个指示顶点是否在队列中的标记数组mark。为了方便查找某个顶点的邻接点，图采用临界表存储。

[cpp] view plain copy

1. Procedure SPFA;  

2.   

3. Begin  

4.    initialize-single-source(G,s);  

5.    initialize-queue(Q);  

6.    enqueue(Q,s);  

7.    while not empty(Q) do begin  

8.       u:=dequeue(Q);  

9.       for each v∈adj do begin  

10.         tmp:=d[v];  

11.         relax(u,v);  

12.         if (tmp<>d[v]) and (not v in Q) then enqueue(Q,v);  

13.         end;  

14.      end;  

15.End;  

1 _! W4 x6 T/ F- H' S; e/ c1 ^

注意：spfa算法只有在不存在负权环的情况下可以正常的结束，如果存在负权环，那么将总有顶点在入队和出队往返，队列无法为空，这种情况下SPFA无法正常结束。可以通过添加一个变量表示每个顶点进入队列的次数，如果大于|v|那么就可以说明存在负权环