ワーシャル–フロイド法

最短経路問題 > ワーシャル–フロイド法

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

概要

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

  • 入力:
    • (有向または無向)グラフ
    • の各辺の長さ
  • 出力:頂点 と頂点 を結ぶ最短経路を全ての に対して出力
  • 計算量:

アイデア

簡単の為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に対して求める。

他の言語で