フロイド–ワーシャル法

目次

インタラクティブ

中間頂点を1つずつ許す全点対最短経路

k を進める自動リセット

有向グラフ

距離行列

	A	B	C	D	E
A	0	∞	∞	∞	∞
B	∞	0	∞	∞	∞
C	∞	∞	0	∞	∞
D	∞	∞	∞	0	∞
E	∞	∞	∞	∞	0

「k を進める」を押して A を中間頂点として許可します。

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

全点対最短経路を求めるフロイド–ワーシャル法

多くの頂点対の距離が必要なとき、単一始点探索を何度も実行するのは非効率なことがあります。フロイド–ワーシャル法は、各頂点を中継点として順に許す動的計画法です。負の辺重みも扱えますが、対象の頂点対に影響する負閉路がなければ、有限な最短距離が定まります。

漸化式と不変条件

頂点に 0 から V - 1 まで番号を付けます。中継頂点 0, ..., k - 1 を処理した時点で、D[i][j] を、処理済み頂点だけを内部中継点に使う i から j への最小経路コストとします。初期状態では中継点を許しません。D[i][i] = 0 とし、直接辺があればその重み（平行辺は最小値）、辺がなければ無限大を設定します。

段階 k の最良経路は k を通らないか、k を通ります。後者は k で二つの部分経路に分けられ、どちらも内部中継点に使えるのは前段階までの頂点です。したがって、次のように更新します。

$$D[i][j]\leftarrow\min(D[i][j],D[i][k]+D[k][j]).$$

1. 段階 k の前 許可された内部中継点: {0, …, k − 1}

   D[i][j] はこれらの頂点だけを内部中継点に使う。

2. k を使って更新 D[i][j] ← min(D[i][j], D[i][k] + D[k][j])

   最短経路は k を避けるか、k で二つに分かれる。

3. 段階 k の後 許可された内部中継点: {0, …, k}

   この段階を完了してから k+1 を許可する。

最外ループは中継頂点 k のループにします。k+1 を許す前に k の段階をすべて更新することが、不変条件を保って漸化式を実装する要点です。

実行可能な C++ 例

次の関数は n >= 0、すべての辺の端点が [0,n) に入り、入力重みと漸化式で生じる有限和が -INF と INF の間かつ int64_t の範囲内であることを前提とします。INF は到達不能を表します。加算前に両方の値が INF でないことを確認します。重み0の辺も有効なので、真偽値で辺の有無を判定してはいけません。例では有向グラフを入力し、到達不能な頂点対には INF を出力します。構造化束縛を使うため、C++17 以降が必要です。

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <tuple>
#include <vector>

using Weight = std::int64_t;
constexpr Weight INF = (Weight{1} << 60);

std::vector<std::vector<Weight>> floydWarshall(
    int n, const std::vector<std::tuple<int, int, Weight>>& edges) {
  std::vector<std::vector<Weight>> dist(n, std::vector<Weight>(n, INF));
  for (int i = 0; i < n; ++i) dist[i][i] = 0;
  for (const auto& [from, to, weight] : edges)
    dist[from][to] = std::min(dist[from][to], weight);

  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] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  return dist;
}

int main() {
  int n, m;
  std::cin >> n >> m;
  std::vector<std::tuple<int, int, Weight>> edges;
  for (int e = 0; e < m; ++e) {
    int from, to;
    Weight weight;
    std::cin >> from >> to >> weight;
    edges.emplace_back(from, to, weight);
  }
  const auto dist = floydWarshall(n, edges);
  for (const auto& row : dist) {
    for (int j = 0; j < n; ++j) {
      if (j) std::cout << ' ';
      if (row[j] == INF) std::cout << "INF";
      else std::cout << row[j];
    }
    std::cout << '\n';
  }
}

入力例:

4 5
0 1 4
0 2 11
1 2 -2
2 3 3
1 3 7

出力:

0 4 2 5
INF 0 -2 1
INF INF 0 3
INF INF INF 0

0 から 3 への最短経路は 0→1→2→3 で、コストは 4-2+3=5 です。負辺はありますが、負閉路はありません。

計算量と負閉路

三重ループの時間計算量は O(V^3)、距離表の空間計算量は O(V^2) です。多くの頂点対の距離が必要な場合に適していますが、始点が一つだけなら単一始点最短経路法のほうが適切なことがあります。

負閉路を繰り返し通ると、経路のコストをいくらでも小さくできます。更新後に dist[v][v] < 0 となる頂点があれば、負閉路が検出されます。ある v が i から到達可能で、さらに v から j へ到達できるなら、頂点対 (i,j) の最短距離は有限値として定まりません。それ以外の場所にある負閉路は、その頂点対には影響しません。影響を受けない対の有限距離は計算できますが、影響を受ける値を有限な最短距離として報告してはいけません。

要点： 中継頂点のループを最外側に置き、到達不能な区間は加算前に除外し、負閉路の影響を頂点対ごとに判断します。