ダイクストラ‐ほう〔‐ハフ〕【ダイクストラ法】
ダイクストラ法
読み方：だいくすとらほう
【英】：Dijkstra's algorithm
【英】：Dijkstra's algorithm
1959年, ダイクストラによって提案された最短路問題を解くための基本的なアルゴリズムの 1つ. すべての枝が非負のときに適用可能. まず, 各点毎に始点からの距離の自明な上限を距離ラベルとして用意し, 適切な順に距離ラベルの修正を繰り返すことにより, 各点までの(最短)距離を順に確定していく. すべての点の距離ラベルが確定したときに終了する. 結果的に始点から全点への最短路の情報が同時に求まる.
「OR事典」の他の用語
| グラフ･ネットワーク： | クラスター分析 グラフ シュタイナー最小木 ダイクストラ法 ダルメジ・メンデルゾーン分解 デルタマトロイド ナップサック問題 |
ダイクストラ法
ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。
概要
ダイクストラ法は、1959年エドガー・ダイクストラによって考案された。 応用範囲は広くOSPFなどのインターネットルーティングプロトコルや、カーナビの経路探索や鉄道の経路案内においても利用されている。
ほかのアルゴリズムとして、
- 最短経路長の推定値を事前に知っているときは、ダイクストラ法の改良版であるA*アルゴリズムを用いて、より効率的に最短経路を求めることができる。
- 辺の重みが全て同一の非負数の場合は幅優先探索がより速く、線形時間で最短路を計算可能である。
- 無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズム[1]によって線形時間での計算が可能であるが、実用性はあまり高くない[要出典]。
- 辺の重みに負数を含む場合はベルマン-フォード法がある。
擬似コード
ダイクストラ法の擬似コードは以下の通りである[2]。始点（スタート）から全てのグラフの頂点への最短経路を求める。
Optimization computes maxima and minima.
| 一般 |
|
|---|---|
| 微分可能 |
|
| 凸縮小化 |
| ||||
|---|---|---|---|---|---|
| 線型 および 二次 |
|
| 系列範例 (Paradigms) | |||||
|---|---|---|---|---|---|
| グラフ理論 |
|
