ダイクストラ‐ほう〔‐ハフ〕【ダイクストラ法】
ダイクストラ法
読み方：だいくすとらほう
【英】：Dijkstra's algorithm
【英】：Dijkstra's algorithm
1959年, ダイクストラによって提案された最短路問題を解くための基本的なアルゴリズムの 1つ. すべての枝が非負のときに適用可能. まず, 各点毎に始点からの距離の自明な上限を距離ラベルとして用意し, 適切な順に距離ラベルの修正を繰り返すことにより, 各点までの(最短)距離を順に確定していく. すべての点の距離ラベルが確定したときに終了する. 結果的に始点から全点への最短路の情報が同時に求まる.
「OR事典」の他の用語
| グラフ･ネットワーク： | クラスター分析 グラフ シュタイナー最小木 ダイクストラ法 ダルメジ・メンデルゾーン分解 デルタマトロイド ナップサック問題 |
ダイクストラ法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/28 21:35 UTC 版)
ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。
- ^ もしも重複を許す実装を行なうなど再訪が生じる場合には計算量が増える。しかしを の中から取り出した値と比較し等しくない場合は再訪と判定でき防ぐことができる。
- ^ Thorup, Mikkel (1999). “Undirected single-source shortest paths with positive integer weights in linear time”. journal of the ACM 46 (3): 362-394. doi:10.1145/316542.316548.
- ^ コルテ & フィーゲン 2009, アルゴリズム 7.1.
- ^ Priority-Queues
- ^ a b コルテ & フィーゲン 2009, p. 185.
[続きの解説]
「ダイクストラ法」の続きの解説一覧
- 1 ダイクストラ法とは
- 2 ダイクストラ法の概要
- 3 アルゴリズムの解説
- 4 参考文献
- 5 関連項目
- ダイクストラ法のページへのリンク
