出典: フリー百科事典『ウィキペディア(Wikipedia)』
ワーシャル–フロイド法の概略は以下の通りである:
入力:
(有向または無向)グラフ
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
E
{\displaystyle E}
の各辺の長さ
出力:頂点
i
{\displaystyle i}
と頂点
j
{\displaystyle j}
を結ぶ最短経路を全ての
i
,
j
∈
V
{\displaystyle i,j\in V}
に対して出力
計算量:
O
(
V
3
)
{\displaystyle O(V^{3})}
簡 単 の 為
V
=
1
,
.
.
.
,
n
{\displaystyle V={1,...,n}}
上 の グ ラ フ
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
の み を 考 え る 。
k
{\displaystyle k}
を
n
{\displaystyle n}
以 下 の 整 数 と し 、
K
=
1
,
.
.
.
,
k
{\displaystyle K={1,...,k}}
と す る 。
G
{\displaystyle G}
の 各 頂 点
i
,
j
{\displaystyle i,j}
に 対 し 、
G
{\displaystyle G}
を
K
∪
{
i
,
j
}
{\displaystyle K\cup \{i,j\}}
に 制 限 し た グ ラ フ 上 で の
i
{\displaystyle i}
か ら
j
{\displaystyle j}
へ の 最 短 経 路 を
p
i
,
j
{\displaystyle p_{i,j}}
と す る 。 ( 経 路 が 無 い 場 合 は
p
i
,
j
=
{\displaystyle p_{i,j}=}
﹁ な し ﹂ と す る 。 )
K
′
=
1
,
.
.
.
,
k
+
1
{\displaystyle K'={1,...,k+1}}
と し 、
G
{\displaystyle G}
を
K
′
∪
{
i
,
j
}
{\displaystyle K'\cup \{i,j\}}
に 制 限 し た グ ラ フ 上 で の
i
{\displaystyle i}
か ら
j
{\displaystyle j}
へ の 最 短 経 路 を
p
i
,
j
′
{\displaystyle p'_{i,j}}
と す る 。
K
′
∪
{
i
,
j
}
{\displaystyle K'\cup \{i,j\}}
内 で の
i
{\displaystyle i}
か ら
j
{\displaystyle j}
へ の 最 短 経 路 は 、
k
+
1
{\displaystyle k+1}
を 経 由 す る か 、 あ る い は
K
∪
{
i
,
j
}
{\displaystyle K\cup \{i,j\}}
内 に あ る か の い ず れ か で あ る の で 、
次 が 成 立 す る こ と が 分 か る 。 た だ し こ こ で 記 号 ﹁
p
|
|
q
{\displaystyle p||q}
﹂ は ﹁ 経 路
p
{\displaystyle p}
を 進 ん だ 後 に 経 路
q
{\displaystyle q}
を 進 む ﹂ と い う 経 路 を 表 す 。
●
p
i
,
j
′
=
p
i
,
k
+
1
|
|
p
k
+
1
,
j
{\displaystyle p'_{i,j}=p_{i,k+1}||p_{k+1,j}}
:
p
i
,
k
+
1
|
|
p
k
+
1
,
j
{\displaystyle p_{i,k+1}||p_{k+1,j}}
が
p
i
,
j
{\displaystyle p_{i,j}}
よ り 短 い 場 合
●
p
i
,
j
′
=
p
i
,
j
{\displaystyle p'_{i,j}=p_{i,j}}
: そ う で な い 場 合 。
よ っ て
K
=
1
,
.
.
.
,
k
{\displaystyle K={1,...,k}}
に 対 す る 最 短 経 路
p
i
,
j
{\displaystyle p_{i,j}}
が 全 て の
i
,
j
{\displaystyle i,j}
に 対 し て 分 か っ て い れ ば 、
K
′
=
1
,
.
.
.
,
k
+
1
{\displaystyle K'={1,...,k+1}}
に 対 す る 最 短 経 路
p
i
,
j
′
{\displaystyle p'_{i,j}}
が 全 て の
i
,
j
{\displaystyle i,j}
に 対 し て 求 ま る 。
ワ ー シ ャ ル – フ ロ イ ド 法 は 以 上 の 考 察 に 基 づ い た ア ル ゴ リ ズ ム で 、
K
{\displaystyle K}
を 空 集 合 に 初 期 化 後 、
K
{\displaystyle K}
に 頂 点
1
,
2
,
.
.
.
,
n
{\displaystyle 1,2,...,n}
を 付 け 加 え て い く こ と で
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
上 の 最 短 経 路 を 全 て の
i
,
j
{\displaystyle i,j}
に 対 し て 求 め る 。
K
{\displaystyle K}
が 空 集 合 の 場 合 、
K
∪
{
i
,
j
}
=
{
i
,
j
}
{\displaystyle K\cup \{i,j\}=\{i,j\}}
上 の
i
{\displaystyle i}
と
j
{\displaystyle j}
を 結 ぶ 最 短 経 路 は 明 ら か に 次 の よ う に な る 。 た だ し 簡 単 の 為 、 各 頂 点
i
,
j
{\displaystyle i,j}
に 対 し 、
i
{\displaystyle i}
と
j
{\displaystyle j}
を 結 ぶ 辺 は 多 く と も 一 本 と し て い る ‥
i
,
j
{\displaystyle i,j}
を 結 ぶ 辺
e
{\displaystyle e}
が あ れ ば 、 最 短 経 路 は
e
{\displaystyle e}
.
そ う で な け れ ば
i
{\displaystyle i}
と
j
{\displaystyle j}
を 結 ぶ 経 路 は
K
∪
{
i
,
j
}
{\displaystyle K\cup \{i,j\}}
に は そ も そ も 存 在 し な い 。
し た が っ て ワ ー シ ャ ル – フ ロ イ ド 法 で は 、
p
i
,
j
{\displaystyle p_{i,j}}
を 上 述 の ル ー ル で
e
{\displaystyle e}
も し く は ﹁ な し ﹂ に 初 期 化 し た 後 、 前 述 の 方 法 で
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
上 の 最 短 経 路 を 全 て の
i
,
j
{\displaystyle i,j}
に 対 し て 求 め る 。
ワ ー シ ャ ル – フ ロ イ ド 法 の 擬 似 コ ー ド を 記 述 す る 。 以 下 で 、 経 路 の 長 さ が 無 限 大 は 経 路 が な い こ と を 意 味 し て い る 。
d
i
,
j
{\displaystyle d_{i,j}}
は
p
i
,
j
{\displaystyle p_{i,j}}
の 長 さ 。
d
i
,
j
{\displaystyle d_{i,j}}
を 更 新 す る 際 、 経 路 も 記 録 す る と 、
p
i
,
j
{\displaystyle p_{i,j}}
も 求 め る こ と が で き る 。
グラフ
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
および各辺
e
∈
E
{\displaystyle e\in E}
の長さ length(e) を入力として受け取る。
// 初期化
for each i
∈
{\displaystyle \in }
{1,...,n}
for each j
∈
{\displaystyle \in }
{1,...,n}
di,j ← i と j を結ぶ辺 e があれば length(e) なければ 無限大
// 本計算
for each k
∈
{\displaystyle \in }
{1,...,n}
for each i
∈
{\displaystyle \in }
{1,...,n}
for each j
∈
{\displaystyle \in }
{1,...,n}
if (di,j > di,k + dk,j )
di,j ← di,k + dk,j
i
{\displaystyle i}
か ら
j
{\displaystyle j}
へ の 最 短 経 路 を
p
i
,
j
{\displaystyle p_{i,j}}
と し 、
u
{\displaystyle u}
と
v
{\displaystyle v}
を
p
i
,
j
{\displaystyle p_{i,j}}
上 の 頂 点 と す る と 、
u
{\displaystyle u}
か ら
v
{\displaystyle v}
へ の 最 短 経 路 ( の 一 つ ) は
p
i
,
j
{\displaystyle p_{i,j}}
を
u
{\displaystyle u}
、
v
{\displaystyle v}
間 に 制 限 し た も の と 一 致 す る 。
し た が っ て
p
i
,
j
{\displaystyle p_{i,j}}
さ え 知 っ て い れ ば
p
u
,
v
{\displaystyle p_{u,v}}
を 計 算 す る 必 要 も な い し 記 憶 す る 必 要 も な い 。
こ の こ と を 利 用 す る と 、 ワ ー シ ャ ル – フ ロ イ ド 法 に お け る 計 算 量 と 記 憶 量 を 大 幅 に 減 ら す こ と が で き る 。
計 算 量 が 増 え て し ま う こ と を 厭 わ な け れ ば 、 さ ら に 記 憶 量 を 減 ら す こ と も で き る 。
k
{\displaystyle k}
を 一 つ 固 定 し 、
K
=
1
,
.
.
.
,
k
{\displaystyle K={1,...,k}}
に 対 す る 最 短 経 路
p
i
,
j
{\displaystyle p_{i,j}}
が 全 て の
i
,
j
{\displaystyle i,j}
に 対 し て 求 ま っ て い る と す る 。
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
に お い て
p
i
,
j
{\displaystyle p_{i,j}}
上 に あ る 全 て の 辺 を 順 に 赤 く 塗 っ て い く 、 と い う 作 業 を 全 て の
i
,
j
{\displaystyle i,j}
に 対 し て 繰 り 返 し 、 最 終 的 に 赤 く な っ た 辺 を 集 め る こ と で で き る
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
の 部 分 グ ラ フ を
P
{\displaystyle P}
と す る 。
P
{\displaystyle P}
さ え あ れ ば 、
p
i
,
j
{\displaystyle p_{i,j}}
を 全 て 復 元 で き る 。
し た が っ て ワ ー シ ャ ル - フ ロ イ ド 法 で は
{
p
i
,
j
}
i
,
j
∪
{
1
,
.
.
.
,
n
}
{\displaystyle \{p_{i,j}\}_{i,j\cup \{1,...,n\}}}
を 全 て 記 憶 し な く て も
P
{\displaystyle P}
の み を 記 憶 し て お け ば よ い 。
( た だ し
P
{\displaystyle P}
か ら
p
i
,
j
{\displaystyle p_{i,j}}
を 復 元 す る の に 計 算 量 が 必 要 で あ る た め 、 計 算 量 が 増 え て し ま う 。
な お 適 切 に 経 路
p
i
,
j
{\displaystyle p_{i,j}}
を 選 べ ば
P
{\displaystyle P}
は 木 に な る の で 、 こ の こ と を 利 用 す れ ば 復 元 に か か る 計 算 量 も あ る 程 度 押 さ え ら れ る 。 )
ワ ー シ ャ ル – フ ロ イ ド 法 は 以 下 の よ う な 問 題 を 解 く の に 利 用 可 能 で あ る :
● 有 向 グ ラ フ で の 最 短 経 路 を 求 め る ︵ フ ロ イ ド の ア ル ゴ リ ズ ム ︶ 。 こ の 場 合 、 全 エ ッ ジ の 重 み を 同 じ 正 の 値 に 設 定 す る 。 通 常 、 1 を 設 定 す る の で 、 あ る 経 路 の 重 み は そ の 経 路 上 に あ る エ ッ ジ の 数 を 表 す 。
● 有 向 グ ラ フ で の 推 移 閉 包 を 求 め る ︵ ワ ー シ ャ ル の ア ル ゴ リ ズ ム ︶ 。 ス テ ィ ー ブ ン ・ ワ ー シ ャ ル の 元 々 の ア ル ゴ リ ズ ム で は 、 重 み な し の グ ラ フ で あ り 、 ブ ー リ ア ン の 隣 接 行 列 が 使 用 さ れ て い た 。 そ の た め 、 加 算 の 代 わ り に 論 理 積 ( A N D ) が 使 わ れ 、 最 小 を 求 め る に は 論 理 和 ( OR ) が 使 用 さ れ て い た 。
● あ る 有 限 オ ー ト マ ト ン に よ り 受 容 さ れ る 正 規 言 語 を 記 述 す る 正 規 表 現 を 探 す ︵ ク リ ー ネ の ア ル ゴ リ ズ ム ︶ 。
● 実 数 の 行 列 の 逆 行 列 を 求 め る ︵ G a u s s - J o r d a n e l i m i n a t i o n ︶ 。
● 最 適 ル ー テ ィ ン グ 。 ネ ッ ト ワ ー ク 上 の 2 つ の ノ ー ド 間 で 通 信 量 が 最 大 な 経 路 を 求 め る と い っ た 用 途 が あ る 。 そ の た め に は 上 掲 の 擬 似 コ ー ド の よ う に 最 小 を 求 め る の で は な く 最 大 を 求 め る よ う に す る 。 エ ッ ジ の 重 み は 通 信 量 の 上 限 を 表 す 。 経 路 の 重 み は ボ ト ル ネ ッ ク に よ っ て 決 ま る 。 し た が っ て 上 掲 の 擬 似 コ ー ド で の 加 算 操 作 は 最 小 を 求 め る 操 作 に 置 き 換 え ら れ る 。
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 .