競プロノート

Appearance

ワーシャルフロイド法（Warshall-Floyd） ​

すべての頂点間の最短距離を O(V³) で求めるアルゴリズム。

負辺があっても利用でき、負閉路の検出も可能。

特徴 ​

項目内容
用途全点対最短経路
適用条件負辺も可
計算量O(V³)
空間計算量O(V²)

考え方 ​

dist[i][j] を頂点 i から j への最短距離とする。

頂点 k を経由する場合としない場合を比較し、距離を更新する。

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

これをすべての k, i, j について繰り返す。

実装 ​

cpp

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

const ll INF = 1LL << 60;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<ll>> dist(n, vector<ll>(n, INF));
    for (int i = 0; i < n; i++) dist[i][i] = 0;

    for (int i = 0; i < m; i++) {
        int a, b;
        ll w;
        cin >> a >> b >> w;
        dist[a][b] = min(dist[a][b], w);
    }

    auto warshall_floyd = [&]() {
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                if (dist[i][k] == INF) continue;
                for (int j = 0; j < n; j++) {
                    if (dist[k][j] == INF) continue;
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    };

    warshall_floyd();

    for (int i = 0; i < n; i++) {
        if (dist[i][i] < 0) {
            cout << "NEGATIVE CYCLE\n";
            return 0;
        }
    }

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

使用例 ​

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

text
4 4
0 1 2
0 2 10
1 2 -1
2 3 3

出力

text
0 2 1 4
INF 0 -1 2
INF INF 0 3
INF INF INF 0

dist[i][j] で、頂点 i から頂点 j への最短距離を取得できる。

注意点 ​

  • 初期状態では dist[i][i] = 0、それ以外は INF にする。
  • 辺が複数存在する場合は、最小の重みを採用する。
  • INF 同士などを加算しないように、到達可能性を確認する。
  • 負辺があっても使用できるが、負閉路の影響を受ける頂点間の最短距離は定義できない。
  • dist[i][i] < 0 となる頂点があれば、負閉路が存在する。
  • 無向グラフの場合は逆向きの辺も追加する。
  • O(V³) なので頂点数が大きい場合は厳しい。
  • 距離の加算によるオーバーフローに注意する。

関連 ​