ダイクストラ法
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/08/02 08:48 UTC 版)

ダイクストラ法(だいくすとらほう、英: Dijkstra's algorithm)はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。
概要
ダイクストラ法は、1959年エドガー・ダイクストラによって考案された。応用範囲は広くOSPFなどのインターネットルーティングプロトコルや、カーナビの経路探索や鉄道の経路案内においても利用されている。
ほかのアルゴリズムとして、
- 最短経路長の推定値を事前に知っているときは、ダイクストラ法の改良版であるA*アルゴリズムを用いて、より効率的に最短経路を求めることができる。
- 辺の重みが全て同一の非負数の場合は幅優先探索がより速く、線形時間で最短路を計算可能である。
- 無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズムによって線形時間での計算が可能であるが[1]、実用性はあまり高くない[要出典]。
- 辺の重みに負数を含む場合はベルマン-フォード法がある。
擬似コード
ダイクストラ法の擬似コードは以下の通りである[2]。始点(スタート)から全てのグラフの頂点への最短経路を求める。
最適化問題では極大・極小値をとる解を求める。
一般 | |
---|---|
微分可能 |
凸最小化 | |||||||
---|---|---|---|---|---|---|---|
線形 および 二次 |
|
系列範例 (Paradigms) |
|||||
---|---|---|---|---|---|
グラフ理論 |
|
||||
フローネットワーク |
|
Weblioに収録されているすべての辞書からダイクストラ法を検索する場合は、下記のリンクをクリックしてください。

- ダイクストラ法のページへのリンク