ワーシャル-フロイド法

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

概要

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

• 入力：
  • (有向または無向)グラフ G=(V, E)
  • Eの各辺の長さ
• 出力：
  • 頂点iと頂点jを結ぶ最短経路を全てのi,j∈Vに対して出力
• 計算量：
  • Θ(n³)。ここでnはGの頂点数。

アイデア

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

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

• p'_i,j = p_i,k+1||p_k+1,j ：p_i,k+1||p_k+1,jがp_i,jより短い場合
• p'_i,j = p_i,j ：そうでない場合。

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

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

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

i,jを結ぶ辺eがあれば、最短経路はe.

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

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

擬似コード

ワーシャル-フロイド法の擬似コードを記述する。 ただし以下で「なし」という経路の長さは無限大であるとみなす。

グラフG=(V,E)および各辺e∈Eの長さw(e)を入力として受け取る。

//初期化

for each i, j ∈ {1,...,n}

if (iとjを結ぶ辺eがある) p_i,j←e

else p_i,j←「なし」

//本計算

for each k ∈ {1,...,n}

for each i,j ∈ {1,...,n}

if (p_i,k+1||p_k+1,jがp_i,jより短い) p_i,j ← p_i,k+1||p_k+1,j

{p_i,j}_{i,j∈{1,...,n}}を出力。

なおp_i,jの長さはp_i,j上の辺の長さの総和なので、入力{w(e)}_e∈Eから簡単に計算できる。

メモリ管理

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

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

応用と一般化

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

• 有向グラフでの最短経路を求める（フロイドのアルゴリズム）。この場合、全エッジの重みを同じ正の値に設定する。通常、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 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