ダイクストラ法（だいくすとらほう、）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。辺の重みに負数を含む場合はベルマン-フォード法などが使える。辺の重みが全て同一の非負数の場合は幅優先探索が速く、線形時間で最短路を計算可能である。また、無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズムによって線形時間での計算が可能であるが、実用性はあまり高くない。ダイクストラ法はグラフ上の2頂点間の最短経路を求めるアルゴリズムで、1959年エドガー・ダイクストラによって考案された。応用範囲は広くOSPFなどのインターネットルーティングプロトコルや、カーナビの経路探索や鉄道の経路案内においても利用されている。なお最短経路の推定値を事前に知っているときは、ダイクストラ法の改良版であるA*アルゴリズムを用いて、より効率的に最短経路を求めることができる。ダイクストラ法の擬似コードは以下の通りである。 formula_1 は頂点の集合（もしくは優先度つきキュー）。 formula_2, formula_3 は頂点。 formula_4 はスタートとなる頂点からの最短経路の長さ。 formula_5 は最短経路をたどる際の前の頂点。「formula_20 から formula_21 が最小である頂点を取り除く」の部分は、オリジナルは単純に集合内を探索するアルゴリズムだが、Q を優先度つきキュー（フィボナッチヒープ）にすることで、より計算量が減る。ただしその場合、Qに関する部分を少し変更する必要がある。下記は優先度つきキューを用いたことを想定し上記を書き換えたダイクストラ法の擬似コードである。「for each ( formula_2 からの辺がある各頂点 formula_11 )」の部分は「for each ( formula_2 からの辺がある各頂点 formula_49 )」でも同じ結果が得られるが、 formula_50 ではあるものの、逆に計算量が増えてしまう場合もあり得ることに注意。GCC の C++ の priority_queue はを使用しているため、これを使うとフィボナッチヒープと同等の計算量のコードが簡単に実装できる。計算量は以下の通り。優先度つきキューを使用した場合の計算量としては、以下の合算である。下記説明は上記擬似コードに基づき、ループ回数も考慮に入れている。話を簡単にするため、G=(V,E)の各頂点v,w∈Vに対し、vとwを結ぶ辺は最大一つしかないとする。vとwを結ぶ辺があれば、その辺を(v,w)と書く。最短経路問題は、ビー玉と紐を用いて解くことができる。まずビー玉を頂点、紐を辺にするグラフを工作する。グラフを板の上に置き、スタートの頂点にあたるビー玉だけをつまむ。グラフが置かれている板を取り除くと、グラフは自由落下を始めるが、スタートにあたるビー玉を持っているので、スタート地点から近いビー玉から順に落下が止まる。ゴールにあたるビー玉が止まったとき、ゴールにあたるビー玉はスタートにあたるビー玉まで紐で一直線で結ばれている。この直線が最短経路である。落下が止まった頂点vに対し、vを支えている頂点wが存在する。wをvの「直前の頂点」と呼ぶことにする。以下簡単のため、直前の頂点は1つしかないと仮定して話を進めるが、一般の場合も同様である。ダイクストラのアルゴリズムは、上述の解法をコンピュータ上でシミュレートしたものである。グラフG=(V,E)、スタートとなる頂点s、および各辺eの長さlength(e)が入力として与えられると、このアルゴリズムは上述の解法をシミュレートし、「落下」が停止した頂点から順に、その頂点の直前の頂点が何であるかを出力する。ゴールとなる頂点の「落下」が停止したところで、ダイクストラのアルゴリズムを止めれば、あとはゴールから順に、直前の頂点、さらにその直前の頂点とたどっていくことで、ゴールとスタートをつなぐ最短経路(の一つ)を求めることができる。以上の考察から分かるように、ダイクストラ法では「次に落下が停止する頂点」（とその直前の頂点）を求めることが重要である。そこでこれらを効率的に求める方法を説明する。現時点で「落下」が停止している頂点の集合をHとし、各頂点v∈Vに対してH∪{v}内でのvとsとの最短距離をd(v)とする（H∪{v}内でsからvに到達できないときはd(v)=∞とする）。さらに、Hに隣接している頂点の集合をAとする。ここで頂点vがHに隣接しているとは、vとH内のいずれかの頂点を結ぶ辺が存在することを指す。次に落下が停止する頂点をuとし、uの直前の頂点をw∈Hとすると、以下が成立することが分かる。そこでダイクストラ法では、「次に落下が停止する頂点」(とその直前の頂点)を効率的に求めるために、以下の3種類のデータを管理する。ダイクストラ法では、A内でd(u)が最小になる頂点u（=次に落下が停止する頂点）を求めてuを出力し、それにあわせて管理しているデータを更新し、そしてさらに次に落下が停止する頂点を求める、という操作を繰り返す。そこで最後に、ダイクストラ法が管理しているデータを更新する方法を述べる。A内でd(u)が最小になる頂点u（=次に落下する頂点）が求まったら、まずuをHに追加する。それにあわせてAからuを除去し、uに隣接していてかつHに属さない頂点をAに加える。uをHに追加した結果「H∪{v}内でのsからvへの最短距離」であるd(v)が変化するのは、uとvとを結ぶ辺がある場合に限られる。uをHに追加後の「H∪{v}内でのsからvへの最短距離」は次のいずれかと一致する。(a)の長さはuをHに追加する前の段階でのd(v)に一致し、一方(b)の長さはuをHに追加する前の段階でのd(u)にlength(u,v)を加えた長さである。以上の考察より、d(v)およびwを次のように更新すればよいことがわかる：

出典:wikipedia