ベルマンフォード最短経路アルゴリズムの性能

Question

ベルマンフォードアルゴリズムの解決策をキューに実装し、その性能をダイクストラアルゴリズムと比較しました。 Bellman - Fordの複雑さはO（NM）なので、彼らはかなり近く、私にとっては驚きでした。私は複雑さが最悪の場合のためであることを知っていますが、依然として結果は驚くべきものでした。 Bellman - Fordについての情報を検索しました.Sedgewick、Javaのアルゴリズム "Bellman-Fordアルゴリズムは通常、線形時間で実行される実際のネットワーク上で"この文しか見つかりませんでした。 Bellman - Fordアルゴリズムのパフォーマンスの動作について説明してください。

Answer 1

これについては、かなり簡単です（PDF Link）。

ベルマン・フォード アルゴリズムの複雑さは エッジ検査、または緩和コールの数に依存します。 （ の緩和ステップと実際の変更が行われたことを参照する とは異なります） 前述のように、 コールの数は、| V || E | BGLの実装は です。実際には、| V || E |よりもはるかに小さい です。平均ケースは です。

擬似コードとそれ以降の分析もリストされています。