转自：Dijkstra、Bellman_Ford、SPFA、Floyd算法复杂度比较

Dijkstra：适用于权值为非负的图的单源最短路径，用斐波那契堆的复杂度O(E+VlgV)

BellmanFord：适用于权值有负值的图的单源最短路径，并且能够检测负圈，复杂度O(VE)

SPFA：适用于权值有负值，且没有负圈的图的单源最短路径，论文中的复杂度O(kE)，k为每个节点进入Queue的次数，且k一般<=2，但此处的复杂度证明是有问题的，其实SPFA的最坏情况应该是O(VE).

Floyd：每对节点之间的最短路径。

 

先给出结论：

(1)当权值为非负时，用Dijkstra。

(2)当权值有负值，且没有负圈，则用SPFA，SPFA能检测负圈，但是不能输出负圈。

(3)当权值有负值，而且可能存在负圈，则用BellmanFord，能够检测并输出负圈。

(4)SPFA检测负环：当存在一个点入队大于等于V次，则有负环，后面有证明。

 

本文针对SPFA算法进行分析。

 

 

本文解决问题有：

(1)证明SPFA算法最坏复杂度。

(2)为什么存在一个点进入队列V次，就说图有负环。

 

SPFA是西安交通大学的段凡丁在1994年与《西安交通大学学报》中发表的“关于最短路径的SPFA快速算法”，他在里面说SPFA速度比Dijkstra快，且运行V次的SPFA速度比Floyd速度快，当时我就产生了疑惑：为什么他这么快，在一些经典的书籍中都没有出现过，也没被提及过。

事实证明SPFA算法是有局限的，他不适用于稠密图，对于特别情况的稠密图，SPFA复杂度和BellmanFord时间一样。

 

最优时间复杂度先不看。

 

下面来证明SPFA最坏时间复杂度：

 

思路：

(1)找出SPFA的最最坏到不可能的情况的复杂度为O(VE)。

(2)找出SPFA确实有图，使得跑SPFA的复杂度为O(VE)。

 

 

我原本想举一个例子来说明SPFA存在O(VE)的情况，但是确实，最坏情况复杂度是不能用举例说明的，谢谢TianMingBu老师的指出。

 

 

证明如果有负环当且仅当存在一个点入队列次数大于等于V次。

 

对于某个点v，我们已知s到v的松弛路径的边的数量最多为V-1。

我这里说的松弛路径指的是：比如s直接松弛v，这样就有一条松弛路径：s->v 。s松弛a，a松弛v，则s->a->v就是一条松弛路径。

 

对于所有s到v的松弛路径来说，当松弛路径边的数量相等时，v只入队一次。

比如有松弛路径：

s->a->x->v

s->b->x->v

s->c->z->v，可以看出v只入队一次。

因为s到v的松弛路径的长度最多可以有V-1种变化，所以v最多入队V-1次。

 

举个例子：

 

假设有一个图，点集为{s,a,b,c,v}，则最多可能的松弛路径有：

s->v

s->a->v

s->b->v

s->c->v

s->a->b->v

s->a->c->v

s->b->c->v

s->a->b->c->v

 

则松弛路径的边数变化有1,2,3,4，所以v入队为4次，即V-1次。

 

 

 

所以我们可以说每个点最多入队V-1次，因此我们求最坏情况为每个点都入队V-1次，所以此时：

 

这里举个最坏情况的例子。

 

 

当然我们可能考虑，当给定一个V的值，E的值，比如E=2V，怎么给出一个图，使得对此图运行SPFA算法的复杂度为O(VE).

我们这里假定图是连通的，所以E>=V-1。

 

方法如下：

(1)我们首先将图组成一个链，即如下图所示：

 

 

这样就用去了V-1条边。

(2)分别添加v0连向v2,v3,....vk的边，我们要添加的这些边的权值要满足v0先更新vk,v0更新vk-1后vk-1还能更新vk，以此类推，如下图所示：

(3)以vk,vk-1,.....v1的顺序添加权值为正无穷的自环，且不断循环，这个步骤是为了保持v1到vk点的出度保持一致，所以这样做，如下图：

 

这样我们就构造了一个能够让SPFA跑出O(VE)的图了，原因如下：

 

因为我们E的值和V的值是不确定的，所以很有可能不能够完成上述的这些构造，我们会分析当没有剩余的边构造上面的步骤(2)时的复杂度（也就是说E<=2V-3，因为第一步连成一个链需要V-1条边，而第二步v0连出去的边需要V-2），和有足够的边能构造上面的图这两种情况。

 

(1)如果E<=2V-3

 

因为E<=2V-3，所以E=O(V)，所以只要能够求出复杂度是O(V^2)，即可说为O(VE).

我们要计算所有点的入队次数和访问的边数。

 

V0出度为 E-V+2，V0入队1次。

V1出度为1，V1入队为1次。

V2出度为1，V2入队为2次（分别为v0松弛v2，v1松弛v2）。

V3出度为1，V3入队为3次。

....

V(e-v+2)出度为1，入队次数为(E-V+2)次。

后面V(e-v+3),V(e-v+4),.....V(k-1)的出度为1，入队次数为E-V+2次。 这些点的个数为V-(E-V+3)-1 = 2V-E-4。

vk出度为0，vk入队为E-V+2次。

 

所以总共的访问的边数为：

 

(2)如果E>2V-3

 

此时构造图的第二步已经完毕，所以后面剩余的边只需要不断添加自环保持出度平衡即可。

 

V0出度为V-1，入队1次。

V1到Vk出度为(E-V+2)/(V-1) 或(E-V+2)/(V-1)+1。

v1到vk的入队次数分别为1,2,3,.....V-1。

 

所以总共访问边数为：

 

 

 

[java] view plain copy

1. package C24;  
2.   
3. import java.util.Iterator;  
4. import java.util.LinkedList;  
5. import java.util.List;  
6.   
7. import C22.GraphFactory;  
8. import C22.Pair;  
9. import C22.Weighted_Adjacent_List;  
10.   
11. public class SPFA {  
12.     public int[] spfa(Weighted_Adjacent_List G,String s){  
13.         return spfa(G,G.getVertexIndex(s));  
14.     }  
15.     public int[] spfa(Weighted_Adjacent_List G,int s){  
16.         //1.创建所要的数据结构  
17.         int size = G.getSize();  
18.         int d[] = new int[size];    //距离估计  
19.         for(int i=0;i<d.length;i++){  
20.             d[i] = Integer.MAX_VALUE;  
21.         }  
22.         List<Integer> Q = new LinkedList<Integer>();  
23.         boolean is_in_queue[] = new boolean[size];  //是否在队列中  
24.         for(int i=0;i<is_in_queue.length;i++){  
25.             is_in_queue[i] = false;  
26.         }  
27.         //2.初始化  
28.         d[s] = 0;  
29.         Q.add(s);  
30.         is_in_queue[s] = true;  
31.         //3.核心  
32.         while(!Q.isEmpty()){  
33.             int u = Q.remove(0);  
34.             is_in_queue[u] = false;  
35.             List<Pair> list = G.getListByVertexIndex(u);  
36.             Iterator<Pair> iter = list.iterator();  
37.             while(iter.hasNext()){  
38.                 Pair vstr = iter.next();  
39.                 int v = G.getVertexIndex(vstr.end);  
40.                 if(d[v]>d[u]+vstr.weight){  
41.                     d[v] = d[u] + vstr.weight;  
42.                     if(!is_in_queue[v]){    //如果松弛的点不在队列中，则加入队列；如果在队列中，则不动  
43.                         Q.add(v);  
44.                         is_in_queue[v] = true;  
45.                     }  
46.                 }  
47.             }  
48.         }  
49.         return d;  
50.     }  
51.     public static void main(String[] args) throws Exception {  
52.         SPFA spfa_alg = new SPFA();  
53.         Weighted_Adjacent_List g = GraphFactory.getWeightedAdjacentListInstance("input\\weighted_graph.txt");  
54.         int[] d = spfa_alg.spfa(g,"s");  
55.         for(int i=0;i<d.length;i++){  
56.             System.out.println(g.getVertexValue(i)+":"+d[i]);  
57.         }  
58.     }  
59. }