ダイクストラ法

提供: ORWiki
2007年7月13日 (金) 13:54時点における122.17.2.240 (トーク)による版 (新しいページ: ''''【だいくすとらほう (Dijkstra's algorithm)】''' 1959年, ダイクストラによって提案された最短路問題を解くための基本的なアルゴリズ...')
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

【だいくすとらほう (Dijkstra's algorithm)】

1959年, ダイクストラによって提案された最短路問題を解くための基本的なアルゴリズムの 1つ. すべての枝が非負のときに適用可能. まず, 各点毎に始点からの距離の自明な上限を距離ラベルとして用意し, 適切な順に距離ラベルの修正を繰り返すことにより, 各点までの(最短)距離を順に確定していく. すべての点の距離ラベルが確定したときに終了する. 結果的に始点から全点への最短路の情報が同時に求まる.