ワーシャル–フロイド法

ワーシャル–フロイド法とは

ワーシャル–フロイド法（Floyd-Warshall Algorithm）は、重み付き有向グラフにおける全頂点間の最短経路を求めるためのアルゴリズムです。このアルゴリズムは、グラフ内のすべての頂点のペアについて、その間の最短経路を同時に計算できるという特徴を持っています。スティーブン・ワーシャルとロバート・フロイドによってそれぞれ独立に考案され、その名前が付けられました。このアルゴリズムは、動的計画法の一例としても知られています。

アルゴリズムの概要

ワーシャル–フロイド法の基本的な考え方は、以下の通りです。

1. 入力: 重み付き有向グラフ G = (V, E) 。ここでVは頂点の集合、Eは辺の集合。各辺には長さ（重み）が割り当てられています。
2. 出力: すべての頂点ペア (i, j) について、頂点 i から頂点 j への最短経路とその長さを求めます。
3. 計算量: アルゴリズムの計算量は O(V^3) です。ここで、V はグラフの頂点数を表します。

アルゴリズムのアイデア

グラフ G = (V, E) において、V = {1, 2, ..., n} とします。任意の整数 k (1 <= k <= n) について、K = {1, 2, ..., k} という頂点の部分集合を考えます。頂点 i から j への最短経路を p(i, j) とし、この経路を頂点集合 K ∪ {i, j} に制限して考えます。さらに、K' = {1, 2, ..., k+1} を考え、同様に頂点 i から j への最短経路を p'(i, j) とします。

このとき、p'(i, j) は次のいずれかになります。

頂点 k+1 を経由しない場合: p'(i, j) = p(i, j)
頂点 k+1 を経由する場合: p'(i, j) = p(i, k+1) + p(k+1, j)

この考え方を基に、kを0からnまで順に増やしていくことで、すべての頂点間の最短経路を計算していきます。

アルゴリズムの詳細

1. 初期化: 各頂点 i, j に対して、iからjへの直接的な辺があればその長さ、なければ無限大を初期値として設定します。
2. 繰り返し計算: すべての頂点kに対して、すべての頂点ペア i, jについて、以下の操作を繰り返します。もし、頂点kを経由した方がiからjへの経路が短くなるならば、その値を更新します。

if d[i][j] > d[i][k] + d[k][j]:
d[i][j] = d[i][k] + d[k][j]

この操作をすべての k, i, j に対して行うことで、最終的にすべてのペアの最短経路が求められます。

擬似コード

// 初期化
for each i in {1,...,n}
for each j in {1,...,n}
d[i][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 (d[i][j] > d[i][k] + d[k][j])
d[i][j] ← d[i][k] + d[k][j]

メモリ管理

ワーシャル–フロイド法は、最短経路そのものを記録する必要がなく、各頂点間の最短距離だけを記録するため、メモリ効率が良いという特徴があります。経路を復元する必要がある場合は、別途経路情報を管理する必要があります。

さらに、最短経路の部分経路も最短経路であるという性質を利用すれば、経路をすべて記録する必要はありません。

応用例

ワーシャル–フロイド法は、様々な分野で応用されています。

最短経路問題: グラフ上のすべての頂点ペア間の最短経路を求める基本的な問題に利用できます。
推移閉包の計算: 有向グラフの推移閉包を求めるために利用できます。
有限オートマトンの正規表現: 有限オートマトンが受理する正規言語を記述する正規表現を求めるのに応用できます。
ネットワークルーティング: ネットワークにおける最適な通信経路を求める際に利用できます。

実装例

多くのプログラミング言語でワーシャル–フロイド法の実装が提供されています。例えば、PythonではNetworkXパッケージで簡単に実装できます。

まとめ

ワーシャル–フロイド法は、グラフ理論において非常に重要なアルゴリズムであり、全頂点間の最短経路を効率的に計算することができます。その実装の容易さと応用の幅広さから、多くの分野で利用されています。

参考文献

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990年). Introduction to Algorithms (first edition ed.). MIT Press and McGraw-Hill.
Floyd, Robert W. (1962年6月). “Algorithm 97: Shortest Path”. Communications of the ACM 5 (6): 345.
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.

もう一度検索