ベルマンフォード法
ダイクストラは知ってるけどベルマンフォード法は知らなかったので自分用にまとめておきます。
ベルマンフォード法
目的
重み付きの有向グラフにおいてあるノードからその他のノードへの最短経路を見つける。
重みが負でもOK。
重みが負の場合、負の重みの閉路が存在すると最短経路がいくらでも小さくなってしまうが、このアルゴリズムは負の閉路が存在するかどうかも検出できる。
アルゴリズム
をノードの集合、をエッジの集合とする。
からへの重みの辺をと表す。
開始ノードからノードへの距離をとする。
最短経路におけるノードの親をと表す。
、その他のノードに対してと初期化する
すべてのに対して以下の操作を行う
なら、をと更新する
また、とする2.の操作を回繰り返す
負の閉路が存在するかを以下の手順でチェックする
各エッジに対してとなる辺があるかどうか確かめる
そのような辺がある場合には、グラフに負の閉路が存在する
負の閉路が存在しない場合にはにからまでの最短距離が格納され、をたどっていくと最短経路が分かります。
具体例
簡単な例があった方が自分は理解しやすいので単純なグラフの例を載せておきます。
以下のようなグラフがあったとします。
ノードからこのアルゴリズムを適用した流れを示します。
、
ループ1回目
エッジ:
なので
エッジ:
なので
エッジ:
なので更新しない
エッジ:
なので
ループ2回目
エッジ:
なので更新しない
エッジ:
なので更新しない
・・・という流れで続きます。
ループを回繰り返すと、というようににちゃんと最短経路の長さが格納されます。
今回は単純な例なので、途中から自明な結果になりましたが、負の重みの閉路を含む例だとダイクストラとの違いが出てきて面白いです。
コード
実装例を載せておきます。
シンプルなアルゴリズムなので実装もしやすいです。
from collections import defaultdict #E = [(u, v, w), ...] def BellmanFord(V, E, s): dist = defaultdict(lambda :10**20) dist[s] = 0 pre = {} for i in range(len(V)): for edge in E: u = edge[0] v = edge[1] w = edge[2] if dist[v] > dist[u] + w: dist[v] = dist[u] + w pre[v] = u #負閉路の検出 is_cycle = False for edge in E: u = edge[0] v = edge[1] w = edge[2] if dist[u] + w < dist[v]: is_cycle = True return (dist, pre, is_cycle)