Bellman - Ford アルゴリズムのソリューションをキューで実装し、そのパフォーマンスを Dijkstra アルゴリズムと比較しました。Bellman - Ford の複雑さは O(NM) であるため、両者はかなり接近していました。複雑さは最悪のケースであることはわかっていますが、それでも結果は驚くべきものでした。Bellman-Ford に関する情報を検索したところ、Sedgewick の Algorithms in Java で「実際のネットワークでは、Bellman-Ford アルゴリズムは通常、線形時間で実行される」というこのステートメントのみが見つかりました。Bellman - Ford アルゴリズムのパフォーマンス動作について説明していただけますか?
3909 次
1 に答える
5
これは非常に簡単な論文です（PDF リンク）。
Bellman-Ford アルゴリズムの複雑さは、エッジ検査または緩和呼び出しの数によって異なります。(これは、実行された実際の変更を参照する緩和ステップとは異なることに注意してください。)前述のように、緩和呼び出しの数は |V ||E| よりも少なくなる可能性があります。BGL 実装で。実際、それは |V ||E| よりもはるかに小さいです。平均的な場合。
疑似コードとさらなる分析もリストされています。
于 2009-06-15T16:51:16.510 に答える