ワーシャル–フロイド法

ワーシャル–フロイド法（）は、重み付き有向グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズムである。名称は考案者であるとロバート・フロイドにちなむ（2人はそれぞれ独立に考案）。フロイドのアルゴリズム、ワーシャルのアルゴリズム、フロイド–ワーシャル法とも呼ばれる。
概要.
ワーシャル–フロイド法の概略は以下の通りである：
アイデア.
簡単の為 formula_7 上のグラフ formula_8 のみを考える。
formula_9 を formula_10 以下の整数とし、formula_11 とする。
formula_12 の 各頂点 formula_13 に対し、formula_12 を formula_15 に制限したグラフ上での formula_3 から formula_4 への最短経路を formula_18 とする。(経路が無い場合は formula_19「なし」とする。)
formula_20 とし、formula_12 を formula_22 に制限したグラフ上での formula_3 から formula_4 への最短経路を formula_25とする。
formula_22 内での formula_3 から formula_4 への最短経路は、formula_29 を経由するか、あるいは formula_15 内にあるかのいずれかであるので、
次が成立することが分かる。ただしここで記号「formula_31」は「経路 formula_32 を進んだ後に経路 formula_33 を進む」という経路を表す。
よって formula_11 に対する最短経路 formula_18 が全ての formula_13 に対して分かっていれば、formula_20 に対する最短経路 formula_25 が全ての formula_13 に対して求まる。
ワーシャル–フロイド法は以上の考察に基づいたアルゴリズムで、formula_44 を空集合に初期化後、formula_44 に頂点 formula_46 を付け加えていくことで formula_8 上の最短経路を全ての formula_13 に対して求める。
formula_44 が空集合の場合、formula_50 上の formula_3 とformula_4 を結ぶ最短経路は明らかに次のようになる。ただし簡単の為、各頂点 formula_13 に対し、formula_3 と formula_4 を結ぶ辺は多くとも一本としている：
したがってワーシャル–フロイド法では、formula_18 を上述のルールで formula_57 もしくは「なし」に初期化した後、前述の方法で formula_8 上の最短経路を全ての formula_13 に対して求める。
擬似コード.
ワーシャル–フロイド法の擬似コードを記述する。以下で、経路の長さが無限大は経路がないことを意味している。formula_66 は formula_18 の長さ。formula_66 を更新する際、経路も記録すると、formula_18 も求めることができる。
 グラフ formula_1 および各辺 formula_71 の長さ length(e) を入力として受け取る。
 // 初期化
 di,j ← i と j を結ぶ辺 e があれば length(e) なければ 無限大
 // 本計算
 if (di,j > di,k + dk,j)
 di,j ← di,k + dk,j
メモリ管理.
formula_3 から formula_4 への最短経路を formula_18 とし、formula_80 と formula_81 を formula_18 上の頂点とすると、formula_80 から formula_81 への最短経路(の一つ)は formula_18 を formula_80、formula_81 間に制限したものと一致する。
したがって formula_18 さえ知っていれば formula_89 を計算する必要もないし記憶する必要もない。
このことを利用すると、ワーシャル–フロイド法における計算量と記憶量を大幅に減らすことができる。
計算量が増えてしまうことを厭わなければ、さらに記憶量を減らすこともできる。
formula_9 を一つ固定し、formula_11 に対する最短経路 formula_18 が全ての formula_13 に対して求まっているとする。
formula_94 において formula_18 上にある全ての辺を順に赤く塗っていく、という作業を全ての formula_13 に対して繰り返し、最終的に赤くなった辺を集めることでできる formula_94 の部分グラフを formula_98 とする。
formula_98 さえあれば、formula_18 を全て復元できる。
したがってワーシャル-フロイド法では formula_101 を全て記憶しなくても
formula_98 のみを記憶しておけばよい。
(ただし formula_98 から formula_18 を復元するのに計算量が必要であるため、計算量が増えてしまう。
なお適切に経路 formula_18 を選べば formula_98 は木になるので、このことを利用すれば復元にかかる計算量もある程度押さえられる。)
応用と一般化.
ワーシャル–フロイド法は以下のような問題を解くのに利用可能である: