Warshall Floyd's algorithm ワーシャル フロイド
2006.05.25 00:08 グラフ 最短経路
All Pairs Shortest Path (APSP) problem (全対最短経路問題) は、グラフ G(V, E) に対して、G に含まれるノードの全てのペアの最短経路(距離)を求める問題です。G に負の重みのあるエッジがなければ、この問題は各ノードを起点として Dijkstra's Algorithm を |V| 回行うことによって解くことができます。この方法のオーダーは O(|V|3) または O(|V|(|E| + |V|)log|V|) となります。
Floyd's algorithm は APSP 問題を O(|V|3) で解くことができます。しかも 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|} とします。
Ak[i, j] をノード Vk = {1, 2, 3, ... k} のみを経由するノード i とノード j の最短コスト、その時の経路の1つを Pk[i, j] とします。Floyd's algorithm は Ak-1 を利用して Ak を求めるということを k = {1, 2, 3, ... |V|} に対して行い、A|V| つまり A[i, j] (および P[i, j])を求めます(Dynamic Programming (動的計画法))。Floyd's algorithm は以下のように数学的帰納法によって証明・説明することができます。
このアルゴリズムを実装する時に、Ak[i, j] を求めるために、3次元のメモリ空間を必要と思うかもしれません。つまり Ak[i, j] の計算中に Ak-1[i, j] の値が変化してしまうのでは?と考えてしまいます。しかし、これは以下の理由により問題はありません。
Ak[k, k] = 0 より、
Ak[i, k] = min( Ak-1[i, k], Ak-1[i, k] + Ak-1[k, k] ) = Ak-1[i, k]
Ak[k, j] = min( Ak-1[k, j], Ak-1[k, j] + Ak-1[k, k] ) = Ak-1[k, j]
よって、ノードの全てのペア [i, j] について Ak-1[i, j] を Ak[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] ); } } } }
| コメント(0) | トラックバック(0) | ↑ページトップ |