ワーシャル-フロイド法

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ワーシャル-フロイド法（Warshall-Floyd Algorithm）は、重み付き有向グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズムである。フロイドのアルゴリズム、ワーシャルのアルゴリズム、フロイド-ワーシャル法とも呼ばれる。

[編集] アルゴリズム

ワーシャル-フロイド法では、重み付き有向グラフ (V, E) を隣接行列の形式で表現したものを入力とする。2つのノード間の経路の重みはその経路を構成するエッジ群の重みの合計である。エッジ E の重みは負の値の場合もあるが、グラフ内には重みが負となる閉路は存在しない。このアルゴリズムはノードの各ペアについて全経路中最小の重みとなる経路を計算で求める。計算量は Θ(n³) となる。このアルゴリズムは以下の観測結果に基づいている。

有向グラフ G のノードを V = {1, 2, 3, 4, ..., n} とし、その部分集合 {1, 2, 3, ..., k} を考える。
V 内の任意のノードのペア i、j について、i から j への全経路のうち中継ノードが全て {1, 2, ..., k} に含まれるものを求め、そのうちで重みが最小の経路 p を得たとする。
このアルゴリズムでは、経路 p と中継ノードが全て {1, 2, ..., k−1} に含まれるときの i から j への最短経路の関係を用いる。
その関係は k が経路 p の中継ノード群に含まれるかどうかに依存する。

以下の擬似コードは入力される有向グラフが隣接行列で表されることを前提としており、直接接続されていないノード間の重みは ∞（無限大）で表され、対角線上の要素（あるノードから自分自身への距離）は 0 で表される。

function fw(int[1..n,1..n] graph) {
    // 初期化
    var int[1..n,1..n] dist := graph
    var int[1..n,1..n] pred
    for i from 1 to n
        for j from 1 to n
            pred[i,j] := nil
            if (dist[i,j] > 0) and (dist[i,j] < Infinity)
                pred[i,j] := i
    // このアルゴリズムのメインループ
    for k from 1 to n
        for i from 1 to n
            for j from 1 to n
                if dist[i,j] > dist[i,k] + dist[k,j]
                    dist[i,j] = dist[i,k] + dist[k,j]
                    pred[i,j] = pred[k,j]
    return ( dist, pred ) // 距離と predecessor 配列
}

[編集] 応用と一般化

ワーシャル-フロイド法は以下のような問題を解くのに利用可能である:

有向グラフでの最短経路を求める（フロイドのアルゴリズム）。この場合、全エッジの重みを同じ正の値に設定する。通常、1 を設定するので、ある経路の重みはその経路上にあるエッジの数を表す。
有向グラフでの推移閉包を求める（ワーシャルのアルゴリズム）。スティーブン・ワーシャルの元々のアルゴリズムでは、重み無しのグラフであり、ブーリアンの隣接行列が使用されていた。そのため、加算の代わりに論理積(AND)が使われ、最小を求めるには論理和(OR)が使用されていた。
有限オートマトンが受容する正規言語で記述された正規表現を探す（クリーネのアルゴリズム）。
実数の行列の逆行列を求める（Gauss-Jordan elimination）。
最適ルーティング。ネットワーク上の2つのノード間で通信量が最大な経路を求めるといった用途がある。そのためには上掲の擬似コードのように最小を求めるのではなく最大を求めるようにする。エッジの重みは通信量の上限を表す。経路の重みはボトルネックによって決まる。したがって上掲の擬似コードでの加算操作は最小を求める操作に置き換えられる。
無向グラフが2部グラフであるかどうかを確認する。

[編集] 実装例

JavaScript による実装: Alex Le's Blog
Python による実装: NetworkX package

[編集] 参考文献

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990年).Introduction to Algorithms, first edition, MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
- Section 26.2, "The Floyd-Warshall algorithm", pp. 558–565;
- Section 26.4, "A general framework for solving path problems in directed graphs", pp. 570–576.
Floyd, Robert W. (1962年6月). "Algorithm 97: Shortest Path". Communications of the ACM 5 (6): 345. DOI: 10.1145/367766.368168.
Kleene, S. C. (1956年). “Representation of events in nerve nets and finite automata”, C. E. Shannon and J. McCarthyAutomata Studies, pp. 3–42, Princeton University Press.
Warshall, Stephen (1962年1月). "A theorem on Boolean matrices". Journal of the ACM 9 (1): 11–12. DOI: 10.1145/321105.321107.