heap+dijkstra与SPFA都是单源最短路的高效算法，到底谁比较快一直各有各的说法。于是心血来潮自己测试了下。
测试工具：cena 0.6
系统: windows vista
CPU: T2130， 1.86Ghz
所有程序中，图用相同格式存储，输入，输出，数据都是静态分配
邻接表参考dd的dinic代码
Dijkstra1: 我写的的支持内部修改的heap，
复杂度O（(V+E)logV）
Dijkstra2: STL的priority_queue,更新之后结点直接加进堆中而不是更新堆内的结点
复杂度: ???
Dijkstra3: 朴素的Dijkstra
复杂度O(V^2+E)
SPFA: 经典的bellmen-ford的优化，用的最常见的写法，自己写的queue
复杂度O(k*E), k接近2
USACO: usaco中butter一题的标程稍作修改，本质与Dijkstra1相似,
复杂度O（(V+E)logV）
TEST 1:2000个点的完全图
输入输出用时：2.15-2.9秒， 平均：2.47
用时（除去平均输入输出时间）
单位：秒：
Dijkstra1: 0.13 0.10
Dijkstra2: 0.05 0.41
Dijkstra3: 0.21 0.18
SPFA: 1.04 0.97
USACO: 0.29 0.40
大规模密集图,大量数据的输入输出占用了大部分时间。单纯计算时间太短难以比较。几种dijkstra都有很好的表现，SPFA由于运行时间对于边数的依赖性，显得逊色不少。
对于Dijkstra1和Dijkstra2 因为是密集图，每次找到一个点后无论是内部更新还是重新插入结点，都要O(log n)的复杂度（虽然插入结点的期望复杂度为O(1)，但是由于是重新插入结点，堆内同时存在的总结点数可能会达到E的数量级，增大了常数），工作量都是较大的，堆的优势没有体现出来。 相比之下，朴素的Dijkstra的表现相当不错。
TEST 2: 100000个结点的链状图
输入输出用时：0.10 – 0.30秒， 平均：0.17
用时（除去平均输入输出时间）
单位：秒：
Dijkstra1: 0.03 0.07
Dijkstra2: 0.04 0.07
Dijkstra3: >10 >10
SPFA: 0.03 0.00
USACO: 0.15 0.18
对于极端的链状图，SPFA无疑是最合适的了。每个结只进队一次，标准的O(E)。朴素的dijkstra对于这样的图就力不从心了：每次循环都过一遍结点，在松弛，，然后发现每次O(V)的时间只松弛了一个点。。
Dijkstra2 由于堆内的结点总数最多有E的数量级，稀疏图里和V接近，劣势没有体现出来。
TEST 3: 20000个结点的稀疏图（每个点100条边）
输入输出用时：2.15-2.40 秒， 平均：2.30
用时（除去平均输入输出时间）
单位：秒：
Dijkstra1: 0.30 0.33
Dijkstra2: 0.39 0.57
Dijkstra3: 2.20 3.26
SPFA: 5.45 5.11
USACO: 0.27 0.33
普通的稀疏图，比TEST 2的密集。 Dijkstra+heap依然是最快的。
比较惊奇的结果是：SPFA居然会比朴素dijkstra还慢……有些出乎预料
原因还没想明白……
TEST 3: 5000个结点的较密集图（每个点500条边）
输入输出用时：2.44-2.99 秒， 平均：2.75
用时（除去平均输入输出时间）
单位：秒：
Dijkstra1: 0.30 0.32
Dijkstra2: 0.39 0.33
Dijkstra3: 0.40 0.40
SPFA: 1.04 1.04
USACO: 0.40 0.19
比较密集的图。SPFA的表现仍然不佳，Dijkstra+heap 任然是王道，朴素dijkstra的劣势逐渐缩小
总结：
Dijkstra1对于各种图都有良好表现，但是编程复杂度较高，需要准备模板。Dijkstra2速度也很不错，普遍略逊于Dijkstra1。Dijkstra3对于密集图有不错的表现。
SPFA表现不尽如人意。但是由于SPFA编程复杂度低，适用于各种图，也可以用来负权环，适合比赛使用。
编程复杂度：SPFA>naive dijkstra>STLheap+dijkstra>heap+dijkstra(越靠前越容易是写)
综合效率： heap+dijkstra>STLheap+dijkstra>SPFA>naive dijkstra
比赛的时候STLheap+dijkstra 和SPFA 是不错的选择
dijkstra1:
dijkstra2:
dijkstra3:
SPFA:
USACO:
版权声明：本文为博主原创文章，未经博主允许不得转载。
觉得自己做的到和不做的到，其实只在一念之间
