ベルマンフォード法 (Bellman-Ford Algorithm)
概要
重み付きグラフ\(G = (V, E)\)の始点\(v_s\)から終点\(v_t\)への最短経路を求める。
辺のコストに負が含まれていても正しく動き、負閉路も検出することができる。
計算量
\(O(|V||E|)\)
実装
# V: グラフの頂点数
# r: 始点
# G[v] = [(w, cost), ...]: 頂点vからコストcostで到達できる頂点w
INF = 10**18
dist = [INF] * V
dist[r] = 0
update = 1
for _ in range(V):
update = 0
for v, e in enumerate(G):
for t, cost in e:
if dist[v] != INF and dist[v] + cost < dist[t]:
dist[t] = dist[v] + cost
update = 1
if not update:
break
else:
# 負閉路検出処理
...