我最近使用两种数据结构对Dijkstra算法的运行时间进行了初步比较，这两种数据结构是基于Java的PriorityQueue(如果没有记错的话，它基于二进制堆)和Fibonacci堆。我使用Java的currentTimeMillis()进行计算。我最终得到的结果非常有趣。这是我的一个测试用例的输出:
Running Dijkstra's with 8 nodes and 27 links
- Execution time with binary heap: 1 miliseconds
- Execution time with Fibonacci heap: 4 miliseconds
诚然，目前我缺少数据集，上面的图表是我最大的图表(我打算很快做更多)。但这有意义吗？我一直认为Fibonacci堆比其他数据结构要快，这是因为它们的摊销运行时间。我不确定这3毫秒的差异来自何处。 (如果有帮助，我可以在Intel Core Ivy Bridge i7-3630M处理器上运行它。)
注意:我偶然发现this thread可能解释了这个问题，尽管我仍然不清楚为什么斐波那契堆版本需要更长的时间。根据该线程，可能是因为我的图不够密集，因此减少键操作的数量不足以使Fibonacci堆的性能真正发挥出来。这是唯一合理的结论，还是我还缺少其他东西？
最佳答案
Fibonacci堆比二进制堆(Java优先级队列中使用的数据结构)在渐近速度上快，因为Dijkstra的算法使用Fibonacci堆将花费O(m + n log n)时间，而使用二进制堆将花费O(m log n)时间。这意味着对于大而密集的图，在最坏的情况下，斐波那契堆将更快。
尽管斐波那契堆的渐近速度比二进制堆快，但它们的常数因子却非常大，并且斐波那契堆的许多基本操作都需要很长时间才能完成。从长远来看，它们的性能将超过二进制堆，但是对于较小的图，常数项可能会很大，以至于斐波那契堆实际上更慢。
其次，比较渐近运行时间(O(m + n log n)与O(m log n))。如果您使用的图是稀疏的(即，m = O(n))，则这两个渐近运行时都是相同的(O(n log n))。在那种情况下，斐波那契堆的理论优势就不存在了，二进制堆可能是更好的选择。
最后，请注意，在这种情况下，big-O表示最坏情况的行为，而不是平均情况。前段时间有一篇论文表明，对于某种类型的随机图，Dijkstra的期望算法所花费的时间远远少于减少键和出队操作的最坏情况。在那种情况下，即使在大图上，二进制堆也可能胜过Fibonacci堆，因为最坏情况下的行为永远不会被触发。
希望这可以帮助!