ワーシャル–フロイド法
ワーシャル–フロイド法（英: Warshall–Floyd Algorithm）は、重み付き有向グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズムである。名称は考案者であるスティーブン・ワーシャルとロバート・フロイドにちなむ（二人はそれぞれ独立に考案）。フロイドのアルゴリズム、ワーシャルのアルゴリズム、フロイド-ワーシャル法とも呼ばれる。
目次
1 概要
1.1 アイデア
2 擬似コード
3 メモリ管理
4 応用と一般化
5 実装例
6 参考文献
7 外部リンク
概要
ワーシャル–フロイド法の概略は以下の通りである：
- 入力：
- (有向または無向)グラフ G=(V,E){displaystyle G=(V,E)}
E{displaystyle E}の各辺の長さ
- (有向または無向)グラフ G=(V,E){displaystyle G=(V,E)}
- 出力：頂点 i{displaystyle i}
と頂点 j{displaystyle j}
を結ぶ最短経路を全ての i,j∈V{displaystyle i,jin V}
に対して出力
- 計算量： O(V3){displaystyle O(V^{3})}
アイデア
簡単の為V={1,...,n}上のグラフG=(V,E)のみを考える。
kをn以下の整数とし、K={1,...,k}とする。
Gの各頂点i,jに対し、GをK∪{i,j}に制限したグラフ上でのiからjへの最短経路をpi,jとする。(経路が無い場合はpi,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 = pi,k+1||pk+1,j ：pi,k+1||pk+1,jがpi,jより短い場合
- p'i,j = pi,j ：そうでない場合。
よってK={1,...,k}に対する最短経路pi,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}にはそもそも存在しない。
したがってワーシャル–フロイド法では、pi,jを上述のルールでeもしくは「なし」に初期化した後、
前述の方法でG=(V,E)上の最短経路を全てのi,jに対して求める。
擬似コード
ワーシャル–フロイド法の擬似コードを記述する。以下で、経路の長さが無限大は経路がないことを意味している。di,j は pi,j の長さ。di,j を更新する際、経路も記録すると、pi,j も求めることができる。
グラフ G = (V, E) および各辺 e ∈ E の長さ length(e) を入力として受け取る。
// 初期化
for each i ∈ {1,...,n}
for each j ∈ {1,...,n}
di,j ← i と j を結ぶ辺 e があれば length(e) なければ 無限大
// 本計算
for each k ∈ {1,...,n}
for each i ∈ {1,...,n}
for each j ∈ {1,...,n}
if (di,j > di,k + dk,j)
di,j ← di,k + dk,j
メモリ管理
iからjへの最短経路をpi,jとし、uとvをpi,j上の頂点とすると、
uからvへの最短経路(の一つ)はpi,jをu、v間に制限したものと一致する。
したがってpi,jさえ知っていればpu,vを計算する必要もないし記憶する必要もない。
このことを利用すると、ワーシャル–フロイド法における計算量と記憶量を大幅に減らすことができる。
計算量が増えてしまうことを厭わなければ、さらに記憶量を減らすこともできる。
kを一つ固定し、K={1,...,k}に対する最短経路pi,jが全てのi,jに対して求まっているとする。
G=(V,E)においてpi,j上にある全ての辺を順に赤く塗っていく、という作業を全てのi,jに対して繰り返し、
最終的に赤くなった辺を集めることでできるG=(V,E)の部分グラフをPとする。
Pさえあれば、pi,jを全て復元できる。
したがってワーシャル-フロイド法では{pi,j}i,j∈{1,...,n}を全て記憶しなくても
Pのみを記憶しておけばよい。
(ただしPからpi,jを復元するのに計算量が必要であるため、計算量が増えてしまう。
なお適切に経路pi,jを選べばPは木になるので、
このことを利用すれば復元にかかる計算量もある程度押さえられる。)
応用と一般化
ワーシャル–フロイド法は以下のような問題を解くのに利用可能である:
- 有向グラフでの最短経路を求める（フロイドのアルゴリズム）。この場合、全エッジの重みを同じ正の値に設定する。通常、1 を設定するので、ある経路の重みはその経路上にあるエッジの数を表す。
- 有向グラフでの推移閉包を求める（ワーシャルのアルゴリズム）。スティーブン・ワーシャルの元々のアルゴリズムでは、重みなしのグラフであり、ブーリアンの隣接行列が使用されていた。そのため、加算の代わりに論理積(AND)が使われ、最小を求めるには論理和(OR)が使用されていた。
- ある有限オートマトンにより受容される正規言語を記述する正規表現を探す（クリーネのアルゴリズム）。
実数の行列の逆行列を求める（Gauss-Jordan elimination）。- 最適ルーティング。ネットワーク上の2つのノード間で通信量が最大な経路を求めるといった用途がある。そのためには上掲の擬似コードのように最小を求めるのではなく最大を求めるようにする。エッジの重みは通信量の上限を表す。経路の重みはボトルネックによって決まる。したがって上掲の擬似コードでの加算操作は最小を求める操作に置き換えられる。
- 無向グラフが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
| ||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||
