使用红/黑树实现Dijkstra的最短路径算法？

Question

我知道Dijkstra的算法实际上是用斐波那契堆实现的。但是它是否也可以使用红黑树实现，并且仍然具有O（m log n）的最坏情况运行时间？

Answer 1

对于初学者来说，实际上看到Dijkstra算法用斐波那契堆实现是很少见的。尽管斐波纳契堆给出了很好的渐近性（O（m + n log n）），但实际上它具有如此高的常数因子，以致其他类型的堆更有效。

至于你的问题 - 是的，你可以使用红黑树作为优先级队列来获得O（m log n）性能。这是有效的，因为您可以在O（log n）时间的红黑树中找到最小元素，并在时间O（log n）上模拟树上的减键操作，方法是先执行删除，然后插入。但是，这可能不如使用标准二进制堆的效率高，因为红黑树具有更差的参考位置和更多的内存开销。更一般地说，每当你需要一个优先级队列时，你总是可以使用一个平衡的二叉搜索树，尽管通常这样做是矫枉过正的。

希望这会有所帮助！

Answer 2

我不会说Dijkstra的算法是用斐波那契堆实现的。事实上，任何堆都可以完成，尽管斐波那契在不同的操作中具有最好的分期复杂性（请记住，尽管这只显示在真的是巨大的图表）。再次使用红黑树会达到相同的计算复杂度，但会有更高的常量，因为使用红黑树更复杂。

该算法所需的只是能够从给定集合中获得最小元素。这就是堆的意思，因此它最适合这个问题。红黑树可以做很多其他的事情，因此更复杂，并在这种特殊情况下变得更糟糕。