グラフの最短パスを動的計画法で見つけるアルゴリズム．
グラフの頂点集合 V．始点から頂点 v までの最短パスの距離が d(v)．P は最短パス長を計算済みの頂点の集合．辺の長さは非負とする．
- d(始点)＝0．その他の頂点 v について d(v)＝∞．P＝φ．
- 集合 V-P 中から，d(v*) を最小にする頂点 v* を一つ見つけ，v* を P に加える．
- v* との間に辺 e＝(v*,w) が存在する全ての w∈V-P について，d(w)＝min{d(w), d(v*)+eの長さ} とする
- P＝V なら終了，そうでなければステップ2へ
アルゴリズム終了時には，始点から各頂点 v までの最短パス長が d(v) に残っている．
計算量は，頂点数 n について O(n)．
-- しましま
関連項目†
リンク集†
関連文献†
![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
