「ワーシャル–フロイド法」の版間の差分
削除された内容 追加された内容
4行目:
==概要==
ワーシャル-フロイド法
[[ランダウの記号|Θ]](n<sup>3</sup>) となる。
===アイデア===
K={1,...,k}とし、各頂点i,jに対し、GをK∪{i,j}に制限したグラフ上でのiからjへの最短経路をp<sub>i,j</sub>とする。
===擬似コード===▼
K'={1,...,k+1}とし、GをK'∪{i,j}に制限したグラフ上でのiからjへの最短経路をp'<sub>i,j</sub>とする。
K'∪{i,j}内でのiからjへの最短経路は、k+1を経由するか、あるいはK∪{i,j}内にあるかのいずれかであるので、
次が成立する事が分かる:
* p'<sub>i,j</sub> = (p<sub>i,k+1</sub>||p<sub>k+1,j</sub> :p<sub>i,k+1</sub>||p<sub>k+1,j</sub>がp<sub>i,j</sub>より短い場合
▲頂点集合Vが{1,...,n}であるグラフG=(V,E)を考える。
* p'<sub>i,j</sub> = p<sub>i,j</sub> :そうでない場合。
ここで記号「p||q」はここで「経路pを進んだ後に経路qを進む」という経路を表す。
よってK={1,...,k}に対する最短経路p<sub>i,j</sub>が全てのi,jに対して分かっていれば、
K'={1,...,k+1}に対する最短経路p<sub>i,j</sub>が全てのi,jに対して求まる。
ワーシャル-フロイド法は以上の考察に基づいたアルゴリズムで、Kを空集合に初期化後、
: G=(V,E)および{w(e)}<sub>e∈E</sub>を入力として受け取る。▼
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}にはそもそも存在しない。
したがってワーシャル-フロイド法では、p<sub>i,j</sub>を上述のルールでeもしくは「なし」に初期化した後、
前述の方法でG=(V,E)上の最短経路を全てのi,jに対して求める。
▲===擬似コード===
ワーシャル-フロイド法の擬似コードを記述する。<!--Gの各辺e∈Eに対してe両端点間の距離をw(e)で表す。-->
ただし以下で「なし」という経路の距離は無限大みなす。
://初期化
:for each i, j ∈ {1,...,n}
:: if (iとjを結ぶ辺eがある)
:: else
://本計算
: for each k ∈ {1,...,n}
:: for each i,j ∈ {1,...,n}
::: if
===メモリ管理===
iからjへの最短経路をp<sub>i,j</sub>とし、uとvをp<sub>i,j</sub>上の頂点とすると、
uからvヘの最短経路(の一つ)はp<sub>i,j</sub>をu、v間に制限したものと一致する。
したがってp<sub>i,j</sub>さえ記憶おけばp<sub>u,v</sub>を記憶する必要は無い。
この事を利用すると、ワーシャル-フロイド法における記憶量を大幅に減らす事ができる。
▲: {dist(i,j)}<sub>i,j∈{1,...,n}</sub>を出力。
<!--
以下の[[擬似コード]]は入力される有向グラフが[[隣接行列]]で表されることを前提としており、直接接続されていない
'''function''' fw('''int'''[1..n,1..n] graph) {
|