Spaghetti Source logo

全点対間最短路 (Floyd Warshall)

説明

Floyd Warshall は隣接行列形式で与えられたグラフの全点対間最短路を求めるアルゴリズムである.負閉路が存在する場合はそれも検出する.

アルゴリズムは次の通り.これまでに得られている始点 i から終点 j までの最短路を d[i][j] とするとき,ある頂点 k が存在して d[i][j] > d[i][k] + d[k][j] のとき d[i][j] を更新する.これを k を 1 から n まで増加させながら実行する.これにより,k 番目のループにおける d[i][j] は高々 k 番目の頂点までを中継点に用いる最短経路となって,動的計画法に基づくアルゴリズムが完成する.なお,d[i][i] < 0 のときは i を含む負閉路があることがわかる.

このアルゴリズムは,本質的にはグラフの二点対 i,j について,その間のすべての経路にわたる経路積の和を計算するものである.この立場において Floyd Warshall は次の形で書くことができる:

for k ∈ V
  for i ∈ V
    for j ∈ V
      f[i,j,k] = ( f[i,k,k-1] * f'[k] * f[k,j,k-1] ) + f[i,j,k-1]

ここで [0..k) が経路が中間点として通れる頂点集合であり,計算終了時には V と一致する.f'[k] は k を含むすべてのループに関する値の和であり,多くの問題では自明に求まる.幾つかの応用では f'[k] を適切に設定することで問題が解けることもある.典型的な問題に対して +, *, f' がどのようになるかを以下に示す.

実際のプログラムはただの三重ループなので計算量は自明に O(V^3) である.しかし,あまりにプログラムが単純な構造を持つため,計算量から推定される最大サイズよりも大きい問題に対しても問題なく動作することが多い.全点対間最短路を出す場合はこのアルゴリズムを用いるのがほとんど確実に正解といえる.

計算量

ソースコード

void shortestPath(const Matrix &g,
    Matrix &dist, vector< vector<int> > &inter) {
  int n = g.size();
  dist = g;
  inter.assign(n, vector<int>(n,-1));
  REP(k, n) REP(i, n) REP(j, n) {
    if (dist[i][j] < dist[i][k] + dist[k][j]) {
      dist[i][j] = dist[i][k] + dist[k][j];
      inter[i][j] = k;
    }
  }
}
void buildPath(const vector< vector<int> > &inter,
    int s, int t, vector<int> &path) {
  int u = inter[s][t];
  if (u < 0) path.push_back(s);
  else buildPath(inter, s, u, path), buildPath(inter, u, s, path);
}
vector<int> buildPath(
    const vector< vector<int> > &inter, int s, int t) {
  vector<int> path;
  buildPath(inter, s, t, path);
  path.push_back(t);
  return path;
}

Verified

前原 貴憲(maehara@prefield.com).

Last Modified: 2007.01.08 08:42:26.