fc2ブログ



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 は以下のように数学的帰納法によって証明・説明することができます。

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] となります。

apsp1.gif

(ii) Pk[i, j] がノード k を経由する場合、Pk[i, j] はノード k によって i → k と k → j の2つの部分路に分けられます。この2つの部分路はどちらも 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] となります。

apsp2.gif

(i)(ii) より、i, j の全ての対に対して、
     Ak[i, j] = min( Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j])
を行い Ak を求めます。

このアルゴリズムを実装する時に、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) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ