ベルマンフォード法

ベルマンフォード法は、コストがついた辺をもつグラフにおいてある始点からある終点までの最短コストの経路を探索するアルゴリズムです. ベルマンフォードはダイクストラと異なり負の値も扱えます.もし一周したコストが負になる箇所があるとそこをぐるぐる回り続けることによっていくらでもコストを避けられるため、そのようなグラフでは解を持ちません.

コストに負の値がない限り、ダイクストラの法が高速なのでベルマンフォード法は使用しません. また、ベルマンフォード法によって負の閉路を検出することができます.

ベルマンフォード法によるアルゴリズム 1. すべての頂点のコストを「無限」に設定する.スタート地点だけコストが0. 2. 辺UVに注目して「頂点Uのコスト」+「辺のコスト」<「頂点Vのコスト」なら頂点Vのコストを「頂点Uのコスト」+「辺のコスト」で更新 3. どのノードで更新したかを記録しておく 4. 2~3を全ての辺に対して行う. 5. 2~4を(頂点の数-1)回行う　か　コストの更新が止まれば終了. 「5」で頂点数V-1回更新するのと、1度の更新で全ての辺E個を更新するため、時間計算量はO(VE)となります.