Warshall Floyd's algorithm ワーシャル フロイド

All Pairs Shortest Path (APSP) problem (全対最短経路問題) は、グラフ G(V, E) に対して、G に含まれるノードの全てのペアの最短経路（距離）を求める問題です。G に負の重みのあるエッジがなければ、この問題は各ノードを起点として Dijkstra's Algorithm を |V| 回行うことによって解くことができます。この方法のオーダーは O(|V|³) または O(|V|(|E| + |V|)log|V|) となります。

Floyd's algorithm は APSP 問題を O(|V|³) で解くことができます。しかも Floyd's algorithm は、G に負の閉路がない限り、G に負の重みを持つエッジが存在しても正しく動作します。負の閉路とは、その閉路を成すエッジの重みの合計が負となっている閉路です（負の閉路をもつとき G に最短経路は存在しません）。さらに、Floyd's algorithm は、G に負の閉路が存在するか否かを判定することができます。アルゴリズムが終了した時点で、G のあるノード v からノード v (それ自身) への最短コストが負になっていれば、G に負の閉路が存在します。

Floyd's algorithm は、ノードの全てのペア [i, j] に対する最短コストを与える配列 A[i, j] を以下の方法で求めます。まず、G(V, E) のノードを {1, 2, 3, ... |V|} とします。

A^k[i, j] をノード V^k = {1, 2, 3, ... k} のみを経由するノード i とノード j の最短コスト、その時の経路の１つを P^k[i, j] とします。Floyd's algorithm は A^k-1 を利用して A^k を求めるということを k = {1, 2, 3, ... |V|} に対して行い、A^|V| つまり A[i, j] (および P[i, j])を求めます（Dynamic Programming (動的計画法)）。Floyd's algorithm は以下のように数学的帰納法によって証明・説明することができます。

1.	A0 ( k = 0 ) の時の証明 A0[i, j] は、ノード i とノード j 以外に経由ノードが存在しないので、単にノード i とノード j を繋ぐエッジの重みになります。つまり、入力されたグラフ G に対応させます。G のノード i からノード j に向かって重み d のエッジがあれば A[i, j] = d とし、エッジがなければ A[i, j] = ∞ とます。これを全対の [i, j] に対して施します。ただし A[i, i] = 0 とします。
	この時点で、A0[i, j] がノード i からノード j への最短コストであることは明白なので、帰納法の基礎が確立できました。
2.	Ak ( k > 0 ) の時の証明 k = {1, 2, 3, ... |V|} について、Ak-1 に基づいて Ak が正しく求められるか？を示します。
	Pk[i, j] がノード k を経由しない場合とする場合を考えます。 (i) Pk[i, j] がノード k を経由しない場合、Pk[i, j] は端点であるノード i とノード j 以外では Vk-1 = {1, 2, 3, ... k-1} に属するノードしか通らないので、Pk-1[i, j] と等しいと考えることができます。よって、この場合は Ak[i, j] = Ak-1[i, j] となります。 (ii) Pk[i, j] がノード k を経由する場合、Pk[i, j] はノード k によって　i → k と k → j の２つの部分路に分けられます。この２つの部分路はどちらも Vk-1 = {1, 2, 3, ... k-1} に属するノードしか経由しません（下図参照）。従ってノード k を経由する最短経路の部分路は Pk-1[i, k] と Pk-1[k, j] となります。つまり、Ak[i, j] = Ak-1[i, k] + Ak-1[k, j] となります。
	(i)(ii) より、i, j の全ての対に対して、      Ak[i, j] = min( Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j]) を行い Ak を求めます。

このアルゴリズムを実装する時に、A^k[i, j] を求めるために、３次元のメモリ空間を必要と思うかもしれません。つまり A^k[i, j] の計算中に A^k-1[i, j] の値が変化してしまうのでは？と考えてしまいます。しかし、これは以下の理由により問題はありません。

A^k[k, k] = 0 より、

     A^k[i, k] = min( A^k-1[i, k], A^k-1[i, k] + A^k-1[k, k] ) = A^k-1[i, k]
     A^k[k, j] = min( A^k-1[k, j], A^k-1[k, j] + A^k-1[k, k] ) = A^k-1[k, j]

よって、ノードの全てのペア [i, j] について A^k-1[i, j] を A^k[i, j] に上書きしても不都合はありません。

int N;
int A[MAX][MAX];

void floyd(){
    for ( int k = 0; k < N; k++ ){
        for ( int i = 0; i < N; i++ ){
            for ( int j = 0; j < N; j++ ){
                A[i][j] = min( A[i][j], A[i][k] + A[k][j] );
            }
        }
    }
}