ベルマンフォード法（Bellman-Ford Algorithm）とは
ベルマンフォード法とは、
です。
最小経路とはスタートからゴールまでに通るパスの和が最小になるもののことです。
以下の例では、AからFまでの最短経路はA→D→E→B→C→Fとなります。
ベルマンフォード法では負の重みを持つ辺が含まれていても適用可能です。
さらに負閉路（負の重みの総和が負になる閉路）の検出もできます。
最短経路を求める方法は他にも、ダイクストラ法やワーシャルフロイドのアルゴリズムなどがあります。
アルゴリズムの概要
1. 初期化
スタート地点を設定し、スタートから各頂点への距離を無限大（∞）に設定します。
ただし、スタート自身の距離は0とします。
2. 辺の隣接ノードの距離を更新
全ての辺の中から、1つを選択します。(辺はどの順番で選んでも問題ありません。)
その辺を確定済みにして、隣接する頂点の距離を更新します。
更新する距離の計算は、
で計算し、これが既存の距離よりも小さい場合に更新します。
これを全ての辺に対して行います。
3. 繰り返し
「2. 辺の隣接ノードの距離を更新」を(頂点の数 – 1)回繰り返します。
全ての頂点の値が変化しなくなり、最短距離が求められます。
2回めの更新
3回目の更新
もし、頂点の値の変化が止まらない場合は負の閉路が存在していると判断できます。
実装(Python)
ベルマンフォード法をpythonで実装した例です。
def bellman_ford(vertices_num, edges, start):
distances = [float("inf")] * vertices_num
distances[start] = 0
# (頂点-1) 回 繰り返し
for _ in range(vertices_num - 1):
for u, v, w in edges: # 辺を順番に処理
new_distancesance = distances[u] + w
if new_distancesance < distances[v]:
distances[v] = new_distancesance
# 負の閉路の検出
for u, v, w in edges:
if distances[u] + w < distances[v]:
print("負の閉路が存在します")
return None
return distances実行してみます。
A = 0
B = 1
C = 2
D = 3
E = 4
F = 5
edges = {
(A, B, 20), (A, D, 5),
(B, A, 20), (B, C, 10), (B, E, 3),
(C, B, 10), (C, F, 7),
(D, A, 5), (D, E, 10),
(E, B, 3), (E, D, 10), (E, F, 25),
(F, C, 7), (F, E, 25),
}
graph = bellman_ford(6, edges, A)
print(graph)[0, 18, 28, 5, 15, 35]
参考文献
コメント