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。
(3)当权值有负值，而且可能存在负圈，则用BellmanFord。

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

SPFA是西安交通大学的段凡丁在1994年与《西安交通大学学报》中发表的“关于最短路径的SPFA快速算法”，他在里面说SPFA速度比Dijkstra快，且运行V次的SPFA速度比Floyd速度快，当时我就产生了疑惑：为什么他这么快，在一些经典的书籍中都没有出现过，也没被提及过。
事实证明SPFA算法是有局限的，他不适用于稠密图，对于特别情况的稠密图，SPFA复杂度和BellmanFord时间一样。

最优时间复杂度先不看。

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

设一个完全图，v0,v1,v2,....vk为节点，设v0为起始点。
首先能够说明，每个节点的出度为E/V，比如4个节点的完全图，每个节点出度为16/4=4。
第一次循环，v0成功松弛了v1,v2,...vk，即将v1、v2、...、vk放入队列，一共V-1个节点进入队列。
第二次循环，v1成功松弛了v2、v3....、vk，即将v2、...、vk放入队列，一共V-2个节点进入队列。
第三次循环以此类推，最后一共：
(V-1)+(V-2)+(V-3)+...+(0)=V(V-1)/2个节点进入队列。
并且每一个节点注定都会出队列，因为队列为空时算法才会终止。
并且在一个节点出队列时都会访问它的出边，所以一共V(V-1)/2个节点出队列，所以访问过V(V-1)/2 * E/V = O(VE)，与BellmanFord算法一样。

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

补充：综合编程 , 其他综合 ,