ベルマン・フォード法は、グラフ理論において、ある始点から各頂点への最短経路を求めるためのアルゴリズムです。ダイクストラ法と同様に最短経路を求めるためのアルゴリズムであり、負の辺があっても対応できる点が特徴です。しかし、ダイクストラ法よりも計算量が多く、大規模なグラフには向きません。ベルマン・フォード法のアルゴリズムは以下の通りです。
- 始点sから各頂点までの距離をd[i]として、d[i]を無限大に初期化する。
- 始点sの距離d[s]を0とする。
- 辺を緩和する。各辺(u, v)について、以下の条件を満たす場合、d[v]を更新する。
- d[v] > d[u] + w(u, v)
- 上記の辺緩和を全ての辺について行う。これをグラフに含まれる辺の数-1回繰り返す。
- 辺の緩和が行われた後、負のサイクルが存在するかを確認する。負のサイクルが存在する場合、最短距離が存在しないため終了する。
このアルゴリズムによって求められるd[i]が、始点sから頂点iまでの最短距離となります。
また、ダイクストラ法については、下記の記事で解説しています。
Pythonの実装例
Pythonでの実装例は以下の通りです。ここでは、グラフは辞書型で表現され、各辺はtupleで表現されます。また、負の辺がある場合でも動作するように、負のサイクルが存在する場合は例外を投げるようにしています。
def bellman_ford(edges, start): # 頂点数 n = len(edges) # 初期化 dist = [float('inf')] * n dist[start] = 0 # 辺の緩和 for _ in range(n - 1): for u, v, w in edges: if dist[u] != float('inf') and dist[v] > dist[u] + w: dist[v] = dist[u] + w # 負のサイクルの検出 for u, v, w in edges: if dist[u] != float('inf') and dist[v] > dist[u] + w: raise ValueError('Negative cycle detected') return dist
このようにして、Pythonでベルマン・フォード法を実行することができます。以下は、具体例としてグラフを用いて実行結果を確認するためのサンプルコードです。
# グラフの例 graph = { 0: [(1, 4), (2, 3)], 1: [(2, -2), (3, 1)], 2: [(3, 2)], 3: [] } # 始点を0として実行 distances = bellman_ford([(u, v, w) for u, edges in graph.items() for v, w in edges], start=0) # 結果の出力 print(distances)
上記のサンプルコードでは、以下のようなグラフを用いて実行しています。
(4) (3)
0 ----- 1 ----- 2
|\ | / |
| \ | / |
(5)| \ | / (2)
| \ | / |
| \ | / |
| \ | / |
3 ----- 4 ----- 5
(1) (3)
このグラフにおいて、始点0から各頂点への最短経路を求めると以下のようになります。
[0, 4, 2, 5, 6, 9]
この結果から、始点0から頂点4までの最短距離は6であることがわかります。以上のように、Pythonでベルマン・フォード法を実装することができます。ただし、ダイクストラ法よりも計算量が多いため、大規模なグラフには向かないことに注意してください。
