ベルマン-フォード法
- 提唱者
- Richard Bellman and Lester R. Ford
- 年
- 1956
- 種類
- algorithm
- 系統
- Graph Algorithms
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
ベルマン-フォード法は、1950年代にリチャード・ベルマンとレスター・R・フォードによって開発された、負の辺重みを持つ加重グラフにおける最短経路計算の基本的なアルゴリズムである。ダイクストラ法とは異なり、負の重みを正しく扱い、負重みサイクルの存在を検出できる。
手法の背後にある直感
このアルゴリズムは、辺を繰り返し緩和(relax)することによって機能する。各辺について、その辺を経由することが、現在知られている最良の経路よりも目的地への短い経路を提供するかどうかをチェックする。このプロセスを、Vを頂点数として、すべての辺に対してV-1回繰り返すことで、アルゴリズムは負の重みがあっても最短経路を見つけることを保証する。重要な洞察は、V頂点のグラフにおける任意の最短経路は最大でV-1個の辺を含むということである。もしV-1回の反復の後も距離が改善されるなら、負のサイクルが存在しなければならない。
歴史学
このアルゴリズムは、リチャード・ベルマンが1958年に動的計画法の原理を用いて開発し、レスター・R・フォードは1956年にネットワークフローのために類似のアプローチを独立に発見した。このアルゴリズムは1960年代にさらに開発・改良され、ネットワークルーティングや経済学への応用が拡大した。現代のバリアントには、Shortest Path Faster Algorithm (SPFA) や特定のグラフ構造に対する様々な最適化が含まれるが、基本的なベルマン-フォードアプローチはアルゴリズム設計における古典的な参照であり続けている。
使うべき場面
負の辺重みを持つグラフで最短経路を計算する場合にベルマン-フォード法を適用する。これは、通貨裁定取引の検出、重みが負になりうるネットワークプロトコル、または負のコストや重みが意味を持つあらゆるアプリケーションに不可欠である。すべての重みが非負である場合は、より効率的なダイクストラ法を使用する。経路を計算せずに負のサイクルを検出するためにも、このアルゴリズムは適切である。
限界と注意点
- 非負重みの場合、ダイクストラ法よりも遅い: O(VE) 対 O((V+E)logV)
- スパースグラフの場合、他のアルゴリズムと比較して効率が低い
- すべての辺を明示的にリスト化する必要があり、暗黙的または動的なグラフには不向き
- 計算を高速化するためのヒューリスティックなガイダンスがない
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 負の辺重みを正しく扱う
- 負重みサイクルの検出、誤った最短経路結果の防止
- 一部の高度な最短経路アルゴリズムよりも理解・実装が容易
- O(VE)の時間で最短経路を見つけることが保証されている
- 有向グラフと無向グラフの両方で機能する(無向グラフでは注意が必要)
応用
- 通貨裁定取引の検出:為替レートグラフにおける収益性の高いサイクルの特定
- ネットワークルーティングプロトコル:リンクコストが変動したり負になったりする可能性のある場合の最短経路計算
- ゲーム理論:ペナルティ辺や割引係数を持つ最短経路問題の解決
- ロボット工学:斥力(負の重み)を持つ環境での経路計画
- 経済的配分:負の項を含むコスト関数を用いた発電量の最適化
- 通信:リンク重みが遅延や品質メトリクスを表す場合の最適な経路の発見
使い方
使い方
ソースへの距離をゼロに、他のすべての距離を無限大に設定する。オプションで、すべての先行ノードをnullに設定する。
V-1回繰り返す:重みwを持つ各辺(u, v)について、distance[u] + w が distance[v] より小さい場合、distance[v] と v の先行ノードを更新する。
すべての辺をもう一度チェックする。いずれかの距離が改善された場合、負重みサイクルが存在する。適切に応じてエラーを返すか、サイクルを特定する。
よくある落とし穴
- 負のサイクルを検出するための追加の反復を実行し忘れること
- 負の辺を持つ無向グラフでアルゴリズムが正しく機能すると仮定すること(仮想的な負のサイクルを作成する可能性がある)
- ダイクストラ法で十分な場合にアルゴリズムを使用し、不必要なパフォーマンス低下を招くこと
よくある質問
なぜアルゴリズムは正確にV-1回の反復を必要とするのか?
V頂点のグラフにおける任意の経路は最大でV-1個の辺を持つ。V-1回反復することで、アルゴリズムは距離情報がグラフ全体に伝播することを可能にする。V回目の反復は、負のサイクルが存在する場合にのみ距離を改善する。
アルゴリズムはどのように負のサイクルを検出できるのか?
V-1回の反復を完了した後、もう一度緩和パスを実行する。いずれかの距離が減少した場合、負のサイクルが存在する。サイクルに関与するノードは、先行ノードポインタを用いた後退によって特定できる。
時間計算量はどうなり、ダイクストラ法と比較してどうなるか?
ベルマン-フォード法はO(VE)の時間で実行される。ここでVは頂点数、Eは辺数である。ダイクストラ法はバイナリヒープを用いてO((V+E)logV)で実行される。ベルマン-フォード法は遅いが負の重みを扱える。ダイクストラ法は高速だが非負の重みを必要とする。
ベルマン-フォード法は負の重みを持つ無向グラフで機能するか?
技術的には可能だが、辺の双方向性により偽の負のサイクルが発生する可能性がある。結果を正しく解釈するには特別な注意が必要である。無向グラフの場合、代替アプローチを検討する。