Bellman-Ford最短路徑算法的性能

Question

我實現了帶有隊列的Bellman-Ford算法的解決方案，並將其性能與Dijkstra算法進行了比較。他們非常接近，這對我來說是一個驚喜，因爲Bellman - Ford的複雜性是O（NM）。我知道複雜性是最壞的情況，但結果仍然令人驚訝。我搜索了關於Bellman - Ford的一些信息，並且我在Sedgewick中發現了這種說法，Java中的算法「在真實網絡上Bellman-Ford算法通常以線性時間運行」。 您能否給我一個Bellman - Ford算法性能行爲的解釋？

Answer 1

這裏有一篇關於它的論文，非常簡單（PDF Link）。

的貝爾曼 - 福特 算法的複雜性取決於 邊檢查，或放鬆的調用次數。 （注意這不同於 鬆弛步驟，其參考 進行的實際改變。） 如上所述，呼叫的鬆弛數 可以小於| V || E |與 的BGL實現。實際上，它是比| V || E |小得多的 。在 平均情況下。

它列出了僞碼和進一步的分析。