ダイクストラ法では扱えない「負の重み」を持つグラフでも使えるのがベルマンフォード法。この記事では、特徴・アルゴリズムの仕組み・実装例・他手法との違いをわかりやすく紹介します！
ベルマンフォード法とは？
ベルマンフォード法は、始点から各ノードへの最短経路を求めるアルゴリズムで、辺の重みが負でも対応できるのが最大の特徴です。
ポイント
- **負の重み（コスト）**があってもOK
- **負の閉路（ループ）**の検出も可能
- ダイクストラ法と違い、貪欲法ではなく動的計画法的なアプローチ
使用シーン
- 料金に割引やペナルティがある経路計算
- 金融・経済システムの評価モデル
- グラフにマイナス要因が含まれるデータ構造の最短ルート探索
アルゴリズムの手順（ざっくり）
1. 初期化
- 始点は0、その他は∞に設定
2. 全辺を「V-1回」繰り返し緩和
- 辺(u→v)の重みwを使って「距離[v] > 距離[u] + w」なら更新
3. 負の閉路の検出（オプション）
- 最後にもう一度全辺をチェック
- もしさらに緩和できるなら、負の閉路あり
可視化イメージ（簡易）
A --(4)--> B --(-2)--> C
\ ^
\--(3)-------------->/このようなグラフでも、ベルマンフォード法なら負の重み（-2）を考慮して正しい最短経路が求められます。
Python実装（簡単な例）
def bellman_ford(graph, V, start):
distance = [float('inf')] * V
distance[start] = 0
# V-1回の緩和
for _ in range(V - 1):
for u, v, w in graph:
if distance[u] != float('inf') and distance[u] + w < distance[v]:
distance[v] = distance[u] + w
# 負の閉路検出
for u, v, w in graph:
if distance[u] != float('inf') and distance[u] + w < distance[v]:
print("負の閉路が存在します")
return None
return distance
# 頂点数と辺の定義（u, v, w）
V = 5
edges = [
(0, 1, 4),
(0, 2, 3),
(1, 2, -2),
(1, 3, 2),
(2, 3, 3),
(3, 4, 2),
]
print(bellman_ford(edges, V, 0))
ダイクストラ法との違い
| 比較項目 | ダイクストラ法 | ベルマンフォード法 |
|---|---|---|
| 負の重み | 対応不可 | 対応可能 |
| 負の閉路検出 | 不可 | 検出可能 |
| 計算量 | O((V + E) log V) | O(VE) |
| 実行速度 | 速い（優先度付きキュー） | 遅い（全辺の繰り返し処理） |
まとめ
- ベルマンフォード法は「負の重みのあるグラフでも最短経路を求められる」万能型
- ダイクストラ法と違って負の閉路検出機能もある
- 実装はシンプルだが、大規模データでは遅くなる点に注意
