我知道实际上 Dijkstra 的算法是使用斐波那契堆实现的。但是它是否也可以使用红黑树来实现，并且仍然具有 O(m log n) 的最坏情况运行时间？
问问题
1179 次
3 回答
9
对于初学者来说，很少能真正看到使用斐波那契堆实现的 Dijkstra 算法。尽管斐波那契堆提供了很好的渐近性能 (O(m + n log n))，但实际上它具有如此高的常数因子，以至于其他类型的堆更有效。
至于您的问题-是的，您可以使用红黑树作为优先级队列来获得 O(m log n) 性能。这是有效的，因为您可以在 O(log n) 时间内找到红黑树中的最小元素，并在 O(log n) 时间内通过先删除再插入来模拟树上的减少键操作。然而，这可能不如使用标准二叉堆高效，因为红黑树的引用局部性更差，内存开销更大。更一般地，当您需要优先级队列时，您总是可以使用平衡二叉搜索树，尽管通常这样做是多余的。
希望这可以帮助！
于 2013-01-24T15:45:35.043 回答
2
我不会说 Dijkstra 的算法是使用斐波那契堆实现的。事实上，任何堆都可以，尽管 Fiboncci 对不同的操作具有最佳的摊销复杂性（请记住，尽管这只显示在非常大的图表中）。再次使用红黑树将实现相同的计算复杂度，但将具有更高的常数，因为使用红黑树更复杂。
该算法所需的只是能够从给定集合中获取最小元素。这就是堆的用途，因此它最适合这个问题。红黑树可以做很多其他事情，因此在这种特殊情况下更复杂并且性能更差。
于 2013-01-24T15:45:01.010 回答
1
这是个有趣的问题。是的，你可以使用红黑树来实现，下面是一个例子：
于 2018-05-22T19:13:28.000 回答