ベルマンフォード法 †

このページは競技プログラミングに興味のある方向けにベルマン-フォード法を簡単に説明するページです

↑

ベルマンフォード法って何？ †

ダイクストラ法では、条件として「全ての辺の重みが非負である」という条件がありました
ベルマンフォード法では「非負の重みの辺をもつグラフ」であっても探索することが出来ます

↑

グラフって何？ †

ダイクストラ法を読んでください
というか、ダイクストラ法を読んでからこのページを読んでください

↑

どういう手順で求めるの？ †

ベルマン-フォード法では各ノードに2つの情報と1つのフラグを付与する必要があります

情報1：スタート地点から各ノードへ移動する「暫定最短距離」
情報2：各ノードへ暫定最短距離で移動する際に直前に経由する「暫定直前経由ノード」
フラグ：更新するノードかどうかを示す「更新フラグ」

(暫定最短距離だとか、暫定直前経由ノードとかは適当に名づけただけです)

この3つを用意したら、以下のステップでスタート地点から終了地点までの最短経路を辺の数E,ノード数Vに対してO(EV)で求めることが出来ます

1.全てのノードの「暫定最短距離」を「∞」に、「更新フラグ」をOFFにする
2.開始ノード(スタート地点)の「暫定最短距離」を0にし「更新フラグ」をONにする
3.「更新フラグ」がONのノードを全列挙するとともに列挙したノードの「更新フラグ」をOFFにします
4.3で列挙した各ノードについて"一つの辺を経由してたどり着くノード"を全て調べ、経由先のノードの「暫定最短距離」について
　A.(経由先の「暫定最短距離」) > (経由元のノードの「暫定最短距離」＋ 辺の重み)
　　「経由先の暫定最短距離」＝「経由元のノードの「暫定最短距離」＋ 辺の重み」とし、
　　　経由先の「暫定直前経由ノード」を経由元のノードとし、「更新フラグ」をONにする

　B.(経由先の「暫定最短距離」) < (経由元のノードの「暫定最短距離」＋ 辺の重み)の場合
　　　とくになにも行いません

5.全てのノードについて「更新フラグ」がOFFであれば、計算終了。そうでないなら3に戻る

これらの操作が終了すると、各ノードにある「暫定最短距離」が開始ノードからそのノードへ行くまでの最短距離に相当し
その経由手順は「暫定直前経由ノード」をさかのぼることで得ることが出来ます

注：更新フラグをOFFにするのは、列挙した直後です。4の直後に「3で列挙したノードの「更新フラグ」をOFF」
という手順だと、4において3で列挙したノードの「暫定最短距離」が更新された場合に問題が発生します

↑

実装したらプログラムがずっと走り続けてるんだけど・・・ †

もし、グラフのある閉路が全体として負の重みをもつ場合、そこをグルグル回ることで更新が繰り返されます。
したがって、負の重みをもつ閉路がある場合は最短距離自体がそもそも存在せず(全て-∞になる)プログラムが終了しません。
しかしながら、(証明は割愛しますが)ベルマンフォード法において、負の重みをもつ閉路が存在しない場合、そのループ回数は(V-1)回で終了します
したがってループ回数をカウントしておき、それが(V-1)を上回ったら(安全のため、もう少し大きな値をとっても構いません)、処理を終了するようにしましょう
そうなったのであれば負の重みをもつ閉路が存在するということになります

トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS