ワーシャル–フロイド法

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

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

概要

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

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

アイデア

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

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

●$p'_{i,j}=p_{i,k+1}||p_{k+1,j}$$p'_{i,j}=p_{i,k+1}||p_{k+1,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}=p_{i,j}$$p'_{i,j}=p_{i,j}$ : そうでない場合。

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

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

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

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

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

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

擬似コード

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

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

// 初期化
for each i $\in$ {1,...,n}
    for each j $\in$ {1,...,n}
        di,j ← i と j を結ぶ辺 e があれば length(e) なければ 無限大

// 本計算
for each k $\in$ {1,...,n}
    for each i $\in$ {1,...,n}
        for each j $\in$ {1,...,n}
            if (di,j > di,k + dk,j)
                di,j ← di,k + dk,j

メモリ管理

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

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

応用と一般化

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

●有向グラフでの最短経路を求める︵フロイドのアルゴリズム︶。この場合、全エッジの重みを同じ正の値に設定する。通常、1を設定するので、ある経路の重みはその経路上にあるエッジの数を表す。

●有向グラフでの推移閉包を求める︵ワーシャルのアルゴリズム︶。スティーブン・ワーシャルの元々のアルゴリズムでは、重みなしのグラフであり、ブーリアンの隣接行列が使用されていた。そのため、加算の代わりに論理積(AND)が使われ、最小を求めるには論理和(OR)が使用されていた。

●ある有限オートマトンにより受容される正規言語を記述する正規表現を探す︵クリーネのアルゴリズム︶。

●実数の行列の逆行列を求める︵Gauss-Jordan elimination︶。

●最適ルーティング。ネットワーク上の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