ワーシャル–フロイド法のソースを表示

{{pathnav|最短経路問題|frame=2}}
'''ワーシャル–フロイド法'''（{{lang-en-short|Floyd–Warshall Algorithm}}）は、重み付き有向[[グラフ理論|グラフ]]の全ペアの[[最短経路問題]]を[[多項式時間]]で解く[[アルゴリズム]]である。名称は考案者である{{仮リンク|スティーブン・ワーシャル|en|Stephen Warshall}}と[[ロバート・フロイド]]にちなむ（2人はそれぞれ独立に考案）。'''フロイドのアルゴリズム'''、'''ワーシャルのアルゴリズム'''、'''フロイド–ワーシャル法'''とも呼ばれる。

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

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

===アイデア===
簡単の為 <math>V={1,...,n}</math> 上のグラフ <math>G=(V,E)</math> のみを考える。

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

* <math>p'_{i,j} = p_{i,k+1}||p_{k+1,j}</math> : <math>p_{i,k+1}||p_{k+1,j}</math> が <math>p_{i,j}</math> より短い場合
* <math>p'_{i,j} = p_{i,j}</math> : そうでない場合。

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

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

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

: <math>i, j</math> を結ぶ辺 <math>e</math> があれば、最短経路は <math>e</math>.
: そうでなければ <math>i</math> と<math>j</math> を結ぶ経路は <math>K\cup\{i,j\}</math> にはそもそも存在しない。

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

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

 グラフ <math>G = (V, E)</math> および各辺 <math>e \in E</math> の長さ length(e) を入力として受け取る。
 
 // 初期化
 '''for each''' i <math>\in</math> {1,...,n}
     '''for each''' j <math>\in</math> {1,...,n}
         d<sub>i,j</sub> &larr; i と j を結ぶ辺 e があれば length(e) なければ 無限大
 
 // 本計算
 '''for each''' k <math>\in</math> {1,...,n}
     '''for each''' i <math>\in</math> {1,...,n}
         '''for each''' j <math>\in</math> {1,...,n}
             '''if''' (d<sub>i,j</sub> > d<sub>i,k</sub> + d<sub>k,j</sub>)
                 d<sub>i,j</sub> &larr; d<sub>i,k</sub> + d<sub>k,j</sub>

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

計算量が増えてしまうことを厭わなければ、さらに記憶量を減らすこともできる。
<math>k</math> を一つ固定し、<math>K={1,...,k}</math> に対する最短経路 <math>p_{i,j}</math> が全ての <math>i, j</math> に対して求まっているとする。
<math>G=(V, E)</math> において <math>p_{i,j}</math> 上にある全ての辺を順に赤く塗っていく、という作業を全ての <math>i, j</math> に対して繰り返し、最終的に赤くなった辺を集めることでできる <math>G=(V, E)</math> の部分グラフを <math>P</math> とする。
<math>P</math> さえあれば、<math>p_{i,j}</math> を全て復元できる。
したがってワーシャル-フロイド法では <math>\{p_{i,j}\}_{i,j\cup\{1,...,n\}}</math> を全て記憶しなくても
<math>P</math> のみを記憶しておけばよい。
(ただし <math>P</math> から <math>p_{i,j}</math> を復元するのに計算量が必要であるため、計算量が増えてしまう。
なお適切に経路 <math>p_{i,j}</math> を選べば <math>P</math> は[[木 (数学)|木]]になるので、このことを利用すれば復元にかかる計算量もある程度押さえられる。)
<!--
以下の[[擬似コード]]は入力される有向グラフが[[隣接行列]]で表されることを前提としており、直接接続されていない頂点間の重みは ∞（[[無限大]]）で表され、対角線上の要素（ある頂点から自分自身への距離）は 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つのノード間で通信量が最大な経路を求めるといった用途がある。そのためには上掲の擬似コードのように最小を求めるのではなく最大を求めるようにする。エッジの重みは通信量の上限を表す。経路の重みはボトルネックによって決まる。したがって上掲の擬似コードでの加算操作は最小を求める操作に置き換えられる。

==実装例==
* [[Javaアプレット|JavaApplet]] による実装: [http://alexle.net/stuff/floyd-algorithm/ Alex Le's Blog]
* [[Python]] による実装: [https://networkx.lanl.gov/ NetworkX] package

==参考文献==
* {{cite book |first=Thomas H. |last=Cormen|coauthors= Leiserson, Charles E.; [[ロナルド・リベスト|Rivest, Ronald L.]]|title = Introduction to Algorithms | edition = first edition | publisher = MIT Press and McGraw-Hill | date = 1990年 | id = 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.
* {{cite journal | first = Robert W. | last = Floyd | authorlink = ロバート・フロイド | title = Algorithm 97: Shortest Path | journal = Communications of the ACM | volume = 5 | issue = 6 | pages = 345 | date = 1962年6月 | id = {{doi|10.1145/367766.368168}} }}
* {{cite book | authorlink = スティーヴン・コール・クリーネ | first = S. C. | last = Kleene | chapter = Representation of events in nerve nets and finite automata | title = Automata Studies | editor = [[クロード・シャノン|C. E. Shannon]] and [[ジョン・マッカーシー|J. McCarthy]] | pages = pp. 3–42 | publisher = Princeton University Press | date = 1956年 }}
* {{cite journal | first = Stephen | last = Warshall | title = A theorem on Boolean matrices | journal = Journal of the ACM | volume = 9 | issue = 1 | pages = 11–12 | date = 1962年1月 | id = {{doi|10.1145/321105.321107}} }}

==外部リンク==
*[http://www.pms.informatik.uni-muenchen.de/lehre/compgeometry/Gosper/shortest_path/shortest_path.html#visualization Interactive animation of Floyd-Warshall algorithm]

{{アルゴリズム}}
{{最適化アルゴリズム}}

{{DEFAULTSORT:わしやるふろいとほう}}
[[Category:組合せ最適化]]
[[Category:グラフ理論]]
[[Category:アルゴリズム]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]