shortest-path - 使用斐波那契堆时 Dijkstra 是否更快？

Question

使用斐波那契堆时 Dijkstra 是否比使用二进制堆更快？

我自己做了一些实现斐波那契堆并在 Dijkstra 中使用它的实验，我还检查了 fibheap 库中现成的斐波那契堆，但没有一个实现能够更快地找到最短路径二叉堆的使用。

我是否可能在某些方面犯了错误，或者在 Dijsktra 中寻找最短路径的情况下，斐波那契堆实际上可能比二进制堆慢？

Answer 1

使用斐波那契堆可以改善算法的渐近运行时间。换句话说，随着图表变得越来越大，最终会达到使用斐波那契堆比使用二进制堆更快的程度。

但是，我听到的传统观点是，在此之前所需的图形大小非常大，因此，出于实际目的，二进制堆总是会更快。