ワーシャル–フロイド法

ワーシャル–フロイド法（英: Floyd–Warshall Algorithm）は、重み付き有向グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズムである。名称は考案者であるスティーブン・ワーシャル（英語版）とロバート・フロイドにちなむ（2人はそれぞれ独立に考案）。フロイドのアルゴリズム、ワーシャルのアルゴリズム、フロイド–ワーシャル法とも呼ばれる。

概要

ワーシャル–フロイド法の概略は以下の通りである：

• 入力：
  • (有向または無向)グラフ ${\displaystyle G=(V,E)}$
  • ${\displaystyle E}$ の各辺の長さ
• 出力：頂点 ${\displaystyle i}$ と頂点 ${\displaystyle j}$ を結ぶ最短経路を全ての ${\displaystyle i,j\in V}$ に対して出力
• 計算量： ${\displaystyle O(V^{3})}$

アイデア

簡単の為 ${\displaystyle V={1,...,n}}$ 上のグラフ ${\displaystyle G=(V,E)}$ のみを考える。

${\displaystyle k}$ を ${\displaystyle n}$ 以下の整数とし、${\displaystyle K={1,...,k}}$ とする。 ${\displaystyle G}$ の 各頂点 ${\displaystyle i,j}$ に対し、${\displaystyle G}$ を ${\displaystyle K\cup \{i,j\}}$ に制限したグラフ上での ${\displaystyle i}$ から ${\displaystyle j}$ への最短経路を ${\displaystyle p_{i,j}}$ とする。(経路が無い場合は ${\displaystyle p_{i,j}=}$「なし」とする。) ${\displaystyle K'={1,...,k+1}}$ とし、${\displaystyle G}$ を ${\displaystyle K'\cup \{i,j\}}$ に制限したグラフ上での ${\displaystyle i}$ から ${\displaystyle j}$ への最短経路を ${\displaystyle p'_{i,j}}$とする。 ${\displaystyle K'\cup \{i,j\}}$ 内での ${\displaystyle i}$ から ${\displaystyle j}$ への最短経路は、${\displaystyle k+1}$ を経由するか、あるいは ${\displaystyle K\cup \{i,j\}}$ 内にあるかのいずれかであるので、 次が成立することが分かる。ただしここで記号「${\displaystyle p||q}$」は「経路 ${\displaystyle p}$ を進んだ後に経路 ${\displaystyle q}$ を進む」という経路を表す。

• ${\displaystyle p'_{i,j}=p_{i,k+1}||p_{k+1,j}}$ : ${\displaystyle p_{i,k+1}||p_{k+1,j}}$ が ${\displaystyle p_{i,j}}$ より短い場合
• ${\displaystyle p'_{i,j}=p_{i,j}}$ : そうでない場合。

よって ${\displaystyle K={1,...,k}}$ に対する最短経路 ${\displaystyle p_{i,j}}$ が全ての ${\displaystyle i,j}$ に対して分かっていれば、${\displaystyle K'={1,...,k+1}}$ に対する最短経路 ${\displaystyle p'_{i,j}}$ が全ての ${\displaystyle i,j}$ に対して求まる。

ワーシャル–フロイド法は以上の考察に基づいたアルゴリズムで、${\displaystyle K}$ を空集合に初期化後、${\displaystyle K}$ に頂点 ${\displaystyle 1,2,...,n}$ を付け加えていくことで ${\displaystyle G=(V,E)}$ 上の最短経路を全ての ${\displaystyle i,j}$ に対して求める。

${\displaystyle K}$ が空集合の場合、${\displaystyle K\cup \{i,j\}=\{i,j\}}$ 上の ${\displaystyle i}$ と${\displaystyle j}$ を結ぶ最短経路は明らかに次のようになる。ただし簡単の為、各頂点 ${\displaystyle i,j}$ に対し、${\displaystyle i}$ と ${\displaystyle j}$ を結ぶ辺は多くとも一本としている：

${\displaystyle i,j}$ を結ぶ辺 ${\displaystyle e}$ があれば、最短経路は ${\displaystyle e}$.

そうでなければ ${\displaystyle i}$ と${\displaystyle j}$ を結ぶ経路は ${\displaystyle K\cup \{i,j\}}$ にはそもそも存在しない。

したがってワーシャル–フロイド法では、${\displaystyle p_{i,j}}$ を上述のルールで ${\displaystyle e}$ もしくは「なし」に初期化した後、前述の方法で ${\displaystyle G=(V,E)}$ 上の最短経路を全ての ${\displaystyle i,j}$ に対して求める。

擬似コード

ワーシャル–フロイド法の擬似コードを記述する。以下で、経路の長さが無限大は経路がないことを意味している。${\displaystyle d_{i,j}}$ は ${\displaystyle p_{i,j}}$ の長さ。${\displaystyle d_{i,j}}$ を更新する際、経路も記録すると、${\displaystyle p_{i,j}}$ も求めることができる。

グラフ ${\displaystyle G=(V,E)}$ および各辺 ${\displaystyle e\in E}$ の長さ length(e) を入力として受け取る。

// 初期化
for each i ${\displaystyle \in }$ {1,...,n}
    for each j ${\displaystyle \in }$ {1,...,n}
        di,j ← i と j を結ぶ辺 e があれば length(e) なければ 無限大

// 本計算
for each k ${\displaystyle \in }$ {1,...,n}
    for each i ${\displaystyle \in }$ {1,...,n}
        for each j ${\displaystyle \in }$ {1,...,n}
            if (di,j > di,k + dk,j)
                di,j ← di,k + dk,j

メモリ管理

${\displaystyle i}$ から ${\displaystyle j}$ への最短経路を ${\displaystyle p_{i,j}}$ とし、${\displaystyle u}$ と ${\displaystyle v}$ を ${\displaystyle p_{i,j}}$ 上の頂点とすると、${\displaystyle u}$ から ${\displaystyle v}$ への最短経路(の一つ)は ${\displaystyle p_{i,j}}$ を ${\displaystyle u}$、${\displaystyle v}$ 間に制限したものと一致する。 したがって ${\displaystyle p_{i,j}}$ さえ知っていれば ${\displaystyle p_{u,v}}$ を計算する必要もないし記憶する必要もない。 このことを利用すると、ワーシャル–フロイド法における計算量と記憶量を大幅に減らすことができる。

計算量が増えてしまうことを厭わなければ、さらに記憶量を減らすこともできる。 ${\displaystyle k}$ を一つ固定し、${\displaystyle K={1,...,k}}$ に対する最短経路 ${\displaystyle p_{i,j}}$ が全ての ${\displaystyle i,j}$ に対して求まっているとする。 ${\displaystyle G=(V,E)}$ において ${\displaystyle p_{i,j}}$ 上にある全ての辺を順に赤く塗っていく、という作業を全ての ${\displaystyle i,j}$ に対して繰り返し、最終的に赤くなった辺を集めることでできる ${\displaystyle G=(V,E)}$ の部分グラフを ${\displaystyle P}$ とする。 ${\displaystyle P}$ さえあれば、${\displaystyle p_{i,j}}$ を全て復元できる。 したがってワーシャル-フロイド法では ${\displaystyle \{p_{i,j}\}_{i,j\cup \{1,...,n\}}}$ を全て記憶しなくても ${\displaystyle P}$ のみを記憶しておけばよい。 (ただし ${\displaystyle P}$ から ${\displaystyle p_{i,j}}$ を復元するのに計算量が必要であるため、計算量が増えてしまう。 なお適切に経路 ${\displaystyle p_{i,j}}$ を選べば ${\displaystyle P}$ は木になるので、このことを利用すれば復元にかかる計算量もある程度押さえられる。)

応用と一般化

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

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

実装例

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

参考文献

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990年). Introduction to Algorithms (first edition ed.). 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”. In C. E. Shannon and J. McCarthy. Automata Studies. Princeton University Press. pp. pp. 3–42 
• Warshall, Stephen (1962年1月). “A theorem on Boolean matrices”. Journal of the ACM 9 (1): 11–12. doi:10.1145/321105.321107. 

外部リンク

• Interactive animation of Floyd-Warshall algorithm

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件（英語版） 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤン楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂シンプレックス法（英語版） 十字法（英語版） レムケの主ピボット操作法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 切断) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）