ワーシャルフロイド法

ワーシャルフロイド法とは

　グラフのすべての頂点の組 (u,v) に対して、u から v への最短距離を求めるアルゴリズム。

　辺のコストが負でもよい。

ワーシャルフロイド法のアルゴリズム

1. 頂点 u から頂点 v への距離 d[u][v] を u から v への辺 (u,v) のコストで初期化、辺がなければ無限大としておく。また、頂点 u から頂点 u 自身への距離 d[u][u] は 0 としておく。


2. 以下の操作を k=0, 1, …, n-1 (頂点数: n) の順に行う。
• グラフのすべての頂点の組 (u,v) に対して、通れる頂点を頂点集合 {0, 1, …, k} ∨ {u, v} の頂点のみに限定したときの最短距離を求め、その距離が d[u][v] より小さければ d[u][v] をその距離で更新。


3. 距離 d[u][u] < 0 となる頂点 u が存在すれば、負閉路が存在する、存在しなければ負閉路も存在しない。

説明

アルゴリズムの 2. の操作 (図)

　例えば、こんなグラフがあったとする。

　例えば、k=2, u=4, v=6 なら、以下の範囲で頂点 u から頂点 v への最短距離を調べる。(頂点集合 {0, 1, 2} ∨ {4, 6})

　これを、(k, u, v)=(0, 0, 0), (0, 0, 1), …, (0, n-1, n-1), (1, 0, 0), …, (1, n-1, n-1), …, (n-1, 0, 0), …, (n-1, n-1, n-1) の順に調べていく。(一応、k が k=0, 1, …, n-1 の順なだけで (k, 0, 0), (k, 0, 1), …, (k, n-1, n-1) は順不同。)

通れる頂点を限定したときの最短距離ってどう求めるの？

　[通れる頂点を頂点集合 {0, 1, …, k} ∨ {u, v} の頂点のみに限定したときの最短距離 (以下、dk[u][v])] は、すべての頂点の組 (u, v) で、[通れる頂点を頂点集合 {0, 1, …, k-1} ∨ {u, v} の頂点のみに限定したときの最短距離 (以下、dk-1[u][v])] を求められていれば簡単に求められる。

　まず、[通れる頂点を頂点集合 {0, 1, …, k} ∨ {u, v} の頂点のみに限定したときの最短距離] には、以下の 2 パターンが考えられる。

• 最短距離の経路で頂点 k を通らない
• 最短距離の経路で頂点 k を通る

なんだ、当たり前じゃん。でも、これを言い換えるとこうなる。

• dk[u][v] = dk-1[u][v]
• dk[u][v] = dk[u][k] + dk[k][v] 

(頂点 k を通らないなら、頂点 k を通れても通れなくても最短距離は変わらないので、最短距離は、k-1 のときと同じ。頂点 k を通るなら、最短で頂点 u から頂点 k まで行って、最短で頂点 k から頂点 v まで行くのが最短。)

　このままだと頂点 k を通る場合、dk を求めるために dk が必要になってしまう。が、dk[u][k] を考えてみると、通れる頂点を頂点集合 {0, 1, …, k} ∨ {u, k} の頂点のみに限定しているわけだが、{u, k} に k が含まれているため、{0, 1, …, k} から k を抜いても同じ集合になる。つまり、{0, 1, …, k} ∨ {u, k} と {0, 1, …, k-1} ∨ {u, k} が同じとわかる。つまり、dk[u][k] = dk-1[u][k] になる。

　同様に、dk[k][v] = dk-1[k][v]。だから、こうなる。

• dk[u][v] = dk-1[u][v]
• dk[u][v] = dk-1[u][k] + dk-1[k][v] 

dk を求めるために dk-1 を使えばよくなった。やったー。

　この 2 パターンしかないので、これのうち距離が短いほうが最短距離になる。

　k-1 のときの最短距離がわかれば k のときの最短距離が求められるので、帰納的に k=n-1 のときまで求められる。k=n-1 のときは、通れる頂点が頂点集合 {0, 1, …, n-1} ∨ {u, v} の頂点のみに限定されるけど、{0, 1, …, n-1} って全頂点だから、グラフ全体を通れる。だから、k=n-1 のときまで求めれば最短距離が求められる。

　ん？ k=0 のときは k-1 = -1 なんだけど？

　k≠0 のときは、頂点集合が {0, 1, …, k-1, k} ∨ {u, v} で、k-1 の頂点集合が {0, 1, …, k-1} ∨ {u, v}。つまり、k を 1 つ減らすということは、{0, 1, …, k-1, k} から k を抜くとことに言い換えられる (dk[k][v] = dk-1[k][v] の証明のときも k を抜いてるだけだし言い換えて大丈夫なはず)。なので、k=0 のとき、頂点集合が {0} ∨ {u, v} なんだから、k-1 の頂点集合は、{} ∨ {u, v} にすればいい。

　ところで、これって頂点 u, v のみを通れる u から v への最短距離だから、辺 (u, v) があれば、辺 (u, v) のコストと同じだし、なければ距離は無限大 (辿りつけない)。だから、アルゴリズムの 1. では [辺 (u,v) のコストで初期化、辺がなければ無限大] に初期化しているのです。

距離 d[u][u] < 0 となる頂点 u が存在すれば、負閉路は存在するの？

　d[u][u] < 0 なら、距離が 0 未満の経路 u → a1 → a2 → … → ax → u (x>0) が存在する。これは負閉路そのものであるので、[距離 d[u][u] < 0 となる頂点 u が存在する→負閉路は存在する]。

　逆に [負閉路は存在する→距離 d[u][u] < 0 となる頂点 u が存在する] は？

　負閉路 u → a0 → … → ax' → … → ax → u (ax' : a0, …, ax のうち頂点番号が1番大きい頂点) を考える。

　k=(ax' の頂点番号) のとき、通れる頂点が頂点集合 {0, 1, …, ax'} ∨ {u, v} の頂点に限定される (定義から、{0, 1, …, ax'} に a0, …, ax はすべて含まれる)。すると、d[u][u] >= 0 なら、d[u][u] は、d[u][(ax' の頂点番号)] + d[(ax' の頂点番号)][u] (<0 (負閉路だから)) で更新される。よって、[負閉路は存在する→距離 d[u][u] < 0 となる頂点 u が存在する] といえる。

　よって、[距離 d[u][u] < 0 となる頂点 u が存在する↔負閉路は存在する] なので、すべての頂点 u で d[u][u] を調べれば、負閉路があるかわかる。

結局ソースコードは？ (C++)

\(O(|V|^3)\)

#include<bits/stdc++.h>

using namespace std;

class WarshallFloyd{
private:
	const long long INF=1ll<<60;  // 無限 (最短距離としてあり得ない値)
	int n;
	vector<vector<long long>> d;  // 距離
	vector<vector<int>> next;  // 経路復元用

public:
	WarshallFloyd(int v):n(v),d(v,vector<long long>(v,INF)),next(v,vector<int>(v,-1)){for(int i=0;i<n;i++)d[i][i]=0;}  // 自分自身への距離を 0 で初期化
	void edge(int from, int to, long long cost){  // [始点 from, 終点 to, コスト cost] の辺の追加 (無向グラフの場合は 2 方向の辺を追加してね)
		if(d[from][to]>cost)d[from][to]=cost;  // 一応、多重辺対応で if 付き
	}

	bool solve(){  // ワーシャルフロイド法を実行 (負閉路があれば true なければ false を返す)
		// 2 パターンの比較と最短距離の更新
		for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<n;k++)if(d[j][k]>d[j][i]+d[i][k])d[j][k]=d[j][i]+d[i][k];
		// d[i][i]<0 があれば負閉路あり
		for(int i=0;i<n;i++)if(d[i][i]<0)return true;
		return false;  // なければ負閉路なし
	}

	vector<vector<long long>>getD(){  // 最短距離を取得
		return d;
	}

	long long getD(int from, int to){  // 頂点 from から頂点 to への最短距離を取得
		return d[from][to];
	}

	vector<int> getPath(int from, int to){  // 頂点 from から頂点 to までの経路を取得
		vector<int> path;
		for(int cur=from;cur!=-1;cur=next[cur][to])path.push_back(cur);
		return path;
	}
};

ダイクストラ法やベルマンフォード法と違って、(簡単に) スタート地点から経路復元できるのがいいよね。

終わり！