ベルマン・フォード法
最終更新
ベルマン・フォード法は始点ノードから他のすべてのノードへの最短経路を求め、Dijkstra とは異なり一部の辺の重みが負であっても機能します。総当たりの緩和によって動作します。すべての辺を繰り返し走査し、その辺を通ると距離が短くなる場合、対象ノードの距離を更新します。上の再生を押すと、暫定距離がパスごとに下がっていく様子が見られます。
すべての辺に対する V - 1 回のパスの後、（辺は最大でも V - 1 本しか持てない）各最短経路が求まっています。これにより計算量は O(V · E) となり、Dijkstra より遅いものの、負の重みを扱え、負の重みの閉路を検出できます（V 回目のパスでまだ辺が緩和されるなら、最短経路は存在しません）。
時間計算量と空間計算量
| 指標 | 計算量 | 備考 |
|---|---|---|
| 時間 | O(V · E) | すべての E 辺に対する V − 1 回のパス |
| 空間 | O(V) | ノードごとに 1 つの距離 |
| 負の重み | 対応 | Dijkstra に対する主な利点 |
| 負の閉路 | 検出可能 | 緩和が起きる V 回目のパスが 1 つを示す |
ステップごとの流れ
| ステップ | 何が起きるか |
|---|---|
| 1 | 始点の距離を 0 に、他はすべて無限大に設定する。 |
| 2 | 次のステップを V − 1 回繰り返す。 |
| 3 | 各辺 (u → v, w) について、dist[u] + w < dist[v] かどうか確認する。 |
| 4 | その場合は緩和する: dist[v] = dist[u] + w とする。 |
| 5 | 1 回の完全なパスで何も変わらなければ早期に停止する。 |
具体例
4 ノード S, A, B, C 上で始点 S、辺 S→A (4)、S→B (5)、A→C (3)、B→A (-3) をこの順に緩和します。距離は S=0、それ以外はすべて ∞ から始まります:
| パス | 距離 [S, A, B, C] | 動作 |
|---|---|---|
| Init | [0, ∞, ∞, ∞] | 始点の距離は 0、他はすべて無限大。 |
| 1 | [0, 2, 5, 7] | S→A を 4、S→B を 5、A→C を 7 に緩和し、次に B→A が A を 5 + (-3) = 2 に下げる。 |
| 2 | [0, 2, 5, 5] | A→C が今度は C を 2 + 3 = 5 に改善する。他の辺は緩和されない。 |
| 3 | [0, 2, 5, 5] | どの辺も緩和されないので距離は確定: A は S→B→A 経由でコスト 2。 |
ベルマン・フォード法を使うべき場面
| 使うべきとき | 避けるべきとき |
|---|---|
| 辺の重みが負になりうる。 | すべての重みが非負である（Dijkstra の方が速い）。 |
| 負の重みの閉路を検出する必要がある。 | グラフが巨大で密である - O(V · E) は遅すぎる。 |
| グラフが小さいか疎である。 | 大きなグラフで始点-終点の単一クエリだけが必要。 |
| シンプルで実装しやすいベースラインが必要。 | 重みが非負で、レイテンシが重要。 |
Bellman-Ford Algorithmのコード
Python, JavaScript, Java, C++, Cによるクリーンで実行可能なBellman-Ford Algorithmの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。
PythonでのBellman-Ford Algorithmのコード
Python
1def bellman_ford(vertices, edges, start):2 dist = {v: float("inf") for v in vertices}3 dist[start] = 04 # Relax every edge V-1 times5 for _ in range(len(vertices) - 1):6 for u, v, w in edges:7 if dist[u] + w < dist[v]:8 dist[v] = dist[u] + w9 # One more pass: any improvement means a negative cycle10 for u, v, w in edges:11 if dist[u] + w < dist[v]:12 raise ValueError("Graph contains a negative-weight cycle")13 return dist14
15
16vertices = ["A", "B", "C", "D", "E"]17edges = [18 ("A", "B", 6), ("A", "C", 7), ("B", "D", 5), ("B", "E", -4),19 ("C", "D", -3), ("D", "B", -2), ("E", "D", 7),20]21
22for node, d in bellman_ford(vertices, edges, "A").items():23 print(f"A -> {node}: {d}")JavaScriptでのBellman-Ford Algorithmのコード
JavaScript
1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3 ["A", "B", 6], ["A", "C", 7], ["B", "D", 5], ["B", "E", -4],4 ["C", "D", -3], ["D", "B", -2], ["E", "A", 2],5];6
7function bellmanFord(source) {8 const dist = Object.fromEntries(nodes.map((n) => [n, Infinity]));9 dist[source] = 0;10 // Relax every edge V-1 times11 for (let i = 0; i < nodes.length - 1; i++) {12 for (const [u, v, w] of edges) {13 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;14 }15 }16 // One more pass: any improvement means a negative cycle17 for (const [u, v, w] of edges) {18 if (dist[u] + w < dist[v]) throw new Error("Negative cycle detected");19 }20 return dist;21}22
23console.log("Shortest distances from A:", bellmanFord("A"));JavaでのBellman-Ford Algorithmのコード
Java
1import java.util.Arrays;2
3public class Main {4 public static void main(String[] args) {5 int n = 5;6 // Directed edges {from, to, weight}; negative weights allowed7 int[][] edges = {8 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {1, 2, 8},9 {2, 4, 9}, {3, 1, -2}, {4, 3, 7}, {2, 3, -3}10 };11 int[] dist = new int[n];12 Arrays.fill(dist, Integer.MAX_VALUE);13 dist[0] = 0;14
15 // Relax every edge V-1 times16 for (int i = 0; i < n - 1; i++) {17 for (int[] e : edges) {18 if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {19 dist[e[1]] = dist[e[0]] + e[2];20 }21 }22 }23
24 // One more pass: any improvement means a negative cycle25 boolean hasNegativeCycle = false;26 for (int[] e : edges) {27 if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {28 hasNegativeCycle = true;29 }30 }31
32 System.out.println("Distances from 0: " + Arrays.toString(dist));33 System.out.println("Negative cycle: " + hasNegativeCycle);34 }35}C++でのBellman-Ford Algorithmのコード
C++
1#include <iostream>2#include <vector>3
4struct Edge {5 int from, to, weight;6};7
8int main() {9 const int INF = 1000000000;10 const int n = 5;11 std::vector<Edge> edges = {12 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},13 {1, 4, -4}, {3, 4, 9}, {2, 1, -2},14 };15 std::vector<int> dist(n, INF);16 dist[0] = 0;17 // Relax every edge V-1 times18 for (int pass = 0; pass < n - 1; ++pass) {19 for (const Edge& e : edges) {20 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {21 dist[e.to] = dist[e.from] + e.weight;22 }23 }24 }25 // One extra pass: any improvement means a negative cycle26 bool negativeCycle = false;27 for (const Edge& e : edges) {28 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {29 negativeCycle = true;30 }31 }32 if (negativeCycle) {33 std::cout << "Negative cycle detected\n";34 } else {35 for (int v = 0; v < n; ++v) {36 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";37 }38 }39 return 0;40}CでのBellman-Ford Algorithmのコード
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7typedef struct {8 int from, to, weight;9} Edge;10
11int main(void) {12 Edge edges[] = {13 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},14 {1, 4, -4}, {3, 4, 9}, {2, 1, -2},15 };16 int m = sizeof(edges) / sizeof(edges[0]);17 int dist[N];18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // Relax every edge V-1 times21 for (int pass = 0; pass < N - 1; pass++) {22 for (int i = 0; i < m; i++) {23 Edge e = edges[i];24 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {25 dist[e.to] = dist[e.from] + e.weight;26 }27 }28 }29 // One extra pass: any improvement means a negative cycle30 bool negativeCycle = false;31 for (int i = 0; i < m; i++) {32 Edge e = edges[i];33 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {34 negativeCycle = true;35 }36 }37 if (negativeCycle) {38 printf("Negative cycle detected\n");39 } else {40 for (int v = 0; v < N; v++) {41 printf("Distance 0 -> %d: %d\n", v, dist[v]);42 }43 }44 return 0;45}ベルマン・フォード法のFAQ
ベルマン・フォード法の時間計算量は?
ベルマン・フォード法は
O(V · E) 時間で動作します。V - 1 回のパスを行い、各パスですべての E 辺を緩和します。これは Dijkstra の O((V + E) log V) より遅く、負の辺の重みに対応するための代償です。Dijkstra ではなくベルマン・フォード法を使うべきなのはいつ?
グラフが負の辺の重みを持ちうる場合、または負の重みの閉路を検出する必要がある場合にベルマン・フォード法を使います。Dijkstra は速いですが、非負の重みでのみ正しく動作します。よくある実用例は、負の閉路が重要となる為替裁定の検出です。
ベルマン・フォード法はどのように負の閉路を検出するのか?
V - 1 回の緩和パスの後、負の閉路が存在しなければすべての最短経路が確定します。さらにもう 1 回のパスでまだ辺を緩和できる場合、到達可能な負の重みの閉路が存在し、最短経路は未定義になります（コストを下げるために無限にループできてしまいます）。ベルマン・フォード法とワーシャル・フロイド法の違いは?
ベルマン・フォード法は単一の始点からの最短経路を
O(V · E) で計算し、ワーシャル・フロイド法はすべての対の最短経路を O(V³) で計算します。密なグラフでは、各始点からベルマン・フォード法を実行するとコストは O(V² · E) になるため、すべての対が必要なときは通常ワーシャル・フロイド法の方が良い選択です。どちらも負の辺を扱え、負の閉路を通知できます。ベルマン・フォード法はなぜちょうど V - 1 回のパスが必要なのか?
負の閉路のないグラフでのどの最短経路も最大
V - 1 本の辺しか使いません。V を超えるノードを訪れる経路はいずれかを繰り返すからです。各パスは各最短経路の少なくとも 1 本の辺が正しく緩和されることを保証するので、V - 1 回のパスですべてを確定できます。よくある誤解は、パスを増やすと結果が改善するというものですが、負の閉路が存在しない限り決して改善しません。ベルマン・フォード法は早期に停止できるか?
はい。すべての辺に対する完全なパスで何も緩和されなければ、すべての距離はすでに最適であり、
V - 1 回のパスに達する前に停止できます。この早期終了の最適化は、早く収束するグラフでしばしば大幅に高速化しますが、最悪計算量は O(V · E) のままです。関連リソース
その他の可視化
