Overview
ベルマン-フォード法は、グラフの最短路問題を解くアルゴリズム。
最短路問題とは
最短路問題では辺にコストの付いた「辺重み付きグラフ」が与えられ、「始点」「終点」が指定されている。始点から終点へ至る路農地、間を通る辺のコストの総和が最も小さいものを求める問題。
1.ベルマン-フォード法の基本
2.ベルマン-フォード法の特徴
3.典型問題を解いてみる
1. ベルマン-フォード法の基本
目的：単一始点からの最短経路を求める
特徴：
- 辺の重みが負でも使える
- 負の閉路（負のサイクル）の検出が可能
- 計算量は $O(V×E) $とやや重め
＜アルゴリズムの流れ＞
1.始点の距離を0、他を∞に初期化
2.辺を V-1回 全て順番に緩和する
3.V回目の緩和で更新が起きたら負の閉路あり
- 「緩和」とは？
dist[v] > dist[u] + costであれば、dist[v] = dist[u] + costに更新する操作
＜基本実装＞
def bellman_ford(N, edges, start):
INF = float('inf')
dist = [INF] * N
dist[start] = 0
for i in range(N - 1):
for u, v, cost in edges:
if dist[u] != INF and dist[v] > dist[u] + cost:
dist[v] = dist[u] + cost
# 負の閉路チェック
for u, v, cost in edges:
if dist[u] != INF and dist[v] > dist[u] + cost:
return None # 負の閉路あり
return dist
実行例
- 入力
- ノード数: N = 4
- 辺リスト:
edges = [ (0, 1, 1), # 頂点0 → 頂点1（コスト1） (1, 2, 2), # 頂点1 → 頂点2（コスト2） (2, 3, 3), # 頂点2 → 頂点3（コスト3） (0, 2, 5) # 頂点0 → 頂点2（コスト5） ]- 始点: start = 0
- 呼び出し
dist = bellman_ford(4, edges, 0) print(dist)# 出力 [0, 1, 3, 6]
2. ベルマン-フォード法の特徴
特徴
- 負の辺を扱える
ダイクストラ法では扱えない「コストがマイナスの辺」も処理できる。 - 負の閉路（負のサイクル）検出ができる
負のコストをぐるぐる回って「無限に小さなコスト」が作れる構造を検出できる。 - 計算量は $O(V × E)$
頂点数が多い・辺が多い場合は遅くなるため、実用的には小〜中規模向け。 - 実装はシンプル
V-1回のループで全辺を順に緩和するだけ。初心者でも構造を理解しやすい。
- 「負の閉路」の意味と注意点
負の閉路とは、始点に戻ってくる経路の合計コストがマイナスになるような閉路のこと。
これがあると、最短距離が定義できなくなる（いくらでも短くできてしまうため）。
実装で V回目の緩和で更新があるかどうか を確認するのはこのため。
応用例
- 通貨の裁定機会（Arbitrage）検出
通貨の交換レートをグラフに見立てて、負の閉路があるかを調べることで「交換すれば得をするループ」を見つけられる。 - スケジュールや依存関係グラフ
タスク間の依存関係に重みを持たせ、遅延や早期完了などを扱う場合、負の重みが必要なことも。 - 交通・時間コストグラフ
一部の移動が「割引き」などでマイナスコストになる場合に使える。 - グラフの最短経路に制約がある場合の補助手法
他のアルゴリズムの前処理やチェックにも使える（例：Johnson法など）。
3. 典型問題を解いてみる
例題1. 負の閉路の検出
問題:
有向グラフが与えられ、負の閉路（コストの合計が負のサイクル）が存在するかを判定する
回答
def bellman_ford(N, edges, start):
INF = float('inf')
dist = [INF] * N
dist[start] = 0
for i in range(N - 1):
for u, v, cost in edges:
if dist[u] != INF and dist[v] > dist[u] + cost:
dist[v] = dist[u] + cost
# 負の閉路チェック
for u, v, cost in edges:
if dist[u] != INF and dist[v] > dist[u] + cost:
return None # 負の閉路あり
return dist
例題2. 負の閉路を含む最短経路
問題:
グラフに負の閉路が存在する場合でも、始点から各頂点への最短距離を求める問題。ただし、負の閉路に到達可能な頂点への距離は定義できない。
回答
import heapq
N, M = map(int, input().split())
jobs = [[] for _ in range(M)]
for _ in range(N):
a, b = map(int, input().split())
if a <= M:
jobs[M - a].append(b)
hq = []
res = 0
for day in range(M):
for b in jobs[day]:
heapq.heappush(hq, -b)
if hq:
res += -heapq.heappop(hq)
print(res)
例題3. 通貨の裁定機会（Arbitrage）の検出
問題:
複数の通貨とその交換レートが与えられたとき、ある通貨を出発点として、交換を繰り返すことで元の通貨に戻ったときに利益が得られるか（裁定機会が存在するか）を判定する。
回答
import sys
from collections import deque
N, M, P = map(int, input().split())
edges = []
for _ in range(M):
a, b, c = map(int, input().split())
edges.append((a - 1, b - 1, P - c))
INF = float('inf')
dist = [INF] * N
dist[0] = 0
for i in range(N - 1):
for u, v, cost in edges:
if dist[u] != INF and dist[v] > dist[u] + cost:
dist[v] = dist[u] + cost
# 負の閉路検出
for i in range(N):
for u, v, cost in edges:
if dist[u] != INF and dist[v] > dist[u] + cost:
print(-1)
sys.exit()
print(max(0, -dist[N - 1]))
例題4. 高さの差によるコスト最小化
問題:
各頂点に高さが設定されたグラフにおいて、特定のルールに従って移動する際のコストを最小化する。
回答
import heapq
N, M = map(int, input().split())
H = list(map(int, input().split()))
graph = [[] for _ in range(N)]
for _ in range(M):
u, v = map(int, input().split())
u -= 1
v -= 1
if H[u] >= H[v]:
graph[u].append((v, H[u] - H[v]))
graph[v].append((u, 2 * (H[u] - H[v])))
else:
graph[u].append((v, 2 * (H[v] - H[u])))
graph[v].append((u, H[v] - H[u]))
INF = float('inf')
dist = [INF] * N
dist[0] = 0
hq = [(0, 0)]
while hq:
d, v = heapq.heappop(hq)
if dist[v] < d:
continue
for to, cost in graph[v]:
if dist[to] > dist[v] + cost:
dist[to] = dist[v] + cost
heapq.heappush(hq, (dist[to], to))
res = 0
for i in range(N):
res = max(res, H[0] - H[i] - dist[i])
print(res)