Nik*_*nka 2 algorithm dijkstra shortest-path red-black-tree data-structures
我知道Dijkstra的算法实际上是使用Fibonacci堆实现的.但它是否也可以使用红黑树实现,并且最坏情况下的运行时间仍为O(m log n)？
对于初学者来说,实际上很难看到Dijkstra的算法是用Fibonacci堆实现的.尽管Fibonacci堆具有很好的渐近性能(O(m + n log n)),但实际上它具有如此高的常数因子,其他类型的堆更有效.
至于你的问题 - 是的,你可以使用红黑树作为优先级队列来获得O(m log n)性能.这是有效的,因为您可以在O(log n)时间内找到红黑树中的最小元素,并通过执行删除然后插入来在时间O(log n)上模拟树上的减少键操作.但是,这可能不如使用标准二进制堆那么有效,因为红黑树具有更差的引用局部性和更多的内存开销.更一般地说,无论何时需要优先级队列,您总是可以使用平衡的二叉搜索树,但通常这样做是过度的.
希望这可以帮助!