競プロノート

Appearance

Bellman-Ford（ベルマンフォード法） ​

負辺を含むグラフで、単一始点最短経路を求めるアルゴリズム。

始点から到達可能な負閉路の検出もできる。

特徴 ​

項目内容
用途単一始点最短経路・負閉路検出
適用条件負辺も可
計算量O(VE)
空間計算量O(V+E)（辺リストを含む）

考え方 ​

すべての辺に対して、距離の更新（緩和）を繰り返す。

辺 u → v の重みを w とすると、

dist[v] = min(dist[v], dist[u] + w)

で更新する。

  • 負閉路がなければ、最大 V-1 回の反復で最短距離が求まる。
  • V 回目にも更新が発生するなら、始点から到達可能な負閉路が存在する。
  • 更新が発生しなければ、その時点で終了できる。

実装 ​

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1LL << 60;

struct Edge {
    int from, to;
    ll cost;
};

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    vector<Edge> edges(m);
    for (auto& [a, b, w] : edges) cin >> a >> b >> w;

    vector<ll> dist(n, INF);
    auto bellman_ford = [&](int s) -> bool {
        dist.assign(n, INF);
        dist[s] = 0;

        for (int i = 0; i < n; i++) {
            bool updated = false;
            for (auto [a, b, w] : edges) {
                if (dist[a] == INF) continue;
                if (dist[b] > dist[a] + w) {
                    dist[b] = dist[a] + w;
                    updated = true;
                    if (i == n - 1) return false;
                }
            }
            if (!updated) break;
        }
        return true;
    };

    if (!bellman_ford(s)) {
        cout << "NEGATIVE CYCLE\n";
        return 0;
    }

    for (int v = 0; v < n; v++) {
        if (dist[v] == INF) cout << "INF\n";
        else cout << dist[v] << '\n';
    }
}

使用例 ​

入力（0-indexed、有向グラフ）

text
5 6 0
0 1 4
0 2 5
1 2 -2
1 3 6
2 3 3
3 4 1

出力

text
0
4
2
5
6

頂点1から頂点2への辺重みは -2 だが、負閉路は存在しないため最短距離を求められる。

注意点 ​

  • Dijkstraと異なり、負辺があっても利用できる。
  • 始点から到達不能な負閉路は、この実装では検出しない。
  • 始点から到達可能な負閉路がある場合、最短距離の結果は利用しない。
  • dist[a] == INF の場合は緩和しない。
  • 無向グラフの場合は逆向きの辺も追加する。
  • 負の重みを持つ無向辺は、両方向に移動できるなら負閉路になる。
  • 距離の加算によるオーバーフローに注意する。
  • INFは想定される最短距離より十分大きく設定する。

関連 ​