ダイクストラ法
(Dijkstra's algorithm から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/04/23 10:17 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 関連項目
このページでは「ウィキペディア」からダイクストラ法を検索した結果を表示しています。
Weblioに収録されているすべての辞書からダイクストラ法を検索する場合は、下記のリンクをクリックしてください。
全ての辞書からダイクストラ法 を検索
Weblioに収録されているすべての辞書からダイクストラ法を検索する場合は、下記のリンクをクリックしてください。
全ての辞書からダイクストラ法 を検索 - ダイクストラ法のページへのリンク
