Wikipedia

「ワーシャル–フロイド法」の版間の差分

履歴の双方向閲覧
← 古い編集新しい編集 →
削除された内容 追加された内容
ビジュアルウィキテキスト
Ertyupoi (会話 | 投稿記録)
791 回編集
編集の要約なし
Ertyupoi (会話 | 投稿記録)
791 回編集
編集の要約なし
1行目:
{{pathnav|最短経路問題|frame=1}}
'''ワーシャル-フロイド法'''（Warshall（{{lang-en-short|Warshall-Floyd Algorithm）Algorithm}}）は、重み付き有向[[グラフ理論|グラフ]]の全ペアの[[最短経路問題]]を[[多項式時間]]で解く[[アルゴリズム]]である。'''フロイドのアルゴリズム'''、'''ワーシャルのアルゴリズム'''、'''フロイド-ワーシャル法'''とも呼ばれる。
 
==概要==
6行目:
 
* 入力：
**(有向または無向)グラフ ''<math>G'' = (''V'', ''E'')</math>
**''<math>E''</math> の各辺の長さ
* 出力：頂点 <math>i</math> と頂点 <math>j</math> を結ぶ最短経路を全ての <math>i,j∈'' j \in V''</math> に対して出力
* 計算量：[[ランダウの記号|Θ]](|''V''| <supmath>O(V^3)</supmath>)
 
===アイデア===
38行目:
前述の方法でG=(V,E)上の最短経路を全てのi,jに対して求める。
 
===擬似コード===
ワーシャル-フロイド法の擬似コードを記述する。以下で、経路の長さが無限大は経路がない事を意味している。d<sub>i,j</sub> は p<sub>i,j</sub> の長さ。d<sub>i,j</sub> を更新する際、経路も記録すると、p<sub>i,j</sub> も求める事が出来る。
 
55行目:
d<sub>i,j</sub> ← d<sub>i,k</sub> + d<sub>k,j</sub>
 
===メモリ管理===
iからjへの最短経路をp<sub>i,j</sub>とし、uとvをp<sub>i,j</sub>上の頂点とすると、
uからvへの最短経路(の一つ)はp<sub>i,j</sub>をu、v間に制限したものと一致する。
「https://ja.wikipedia.org/wiki/ワーシャル–フロイド法」から取得