使用紅/黑樹實現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的算法是用斐波那契堆實現的。事實上，任何堆都可以完成，儘管斐波那契在不同的操作中具有最好的分期複雜性（請記住，儘管這隻顯示在真的是巨大的圖表）。再次使用紅黑樹會達到相同的計算複雜度，但會有更高的常量，因爲使用紅黑樹更復雜。

該算法所需的只是能夠從給定集合中獲得最小元素。這就是堆的意思，因此它最適合這個問題。紅黑樹可以做很多其他的事情，因此更復雜，並在這種特殊情況下變得更糟糕。