ダイクストラ法

ダイクストラ法（だいくすとらほう、）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。
これらに対し、辺の重みに負数を含む場合はベルマン-フォード法などが使える。
概要.
ダイクストラ法はグラフ上の2頂点間の最短経路を求めるアルゴリズムで、1959年エドガー・ダイクストラによって考案された。
応用範囲は広くOSPFなどのインターネットルーティングプロトコルや、カーナビの経路探索や鉄道の経路案内においても利用されている。
なお最短経路長の推定値を事前に知っているときは、ダイクストラ法の改良版であるA*アルゴリズムを用いて、より効率的に最短経路を求めることができる。
擬似コード.
ダイクストラ法の擬似コードは以下の通りである。始点（スタート）から全てのグラフの頂点への最短経路を求める。
 // 初期化 
 各頂点 formula_11 に対し、formula_12 ならば formula_13 、それ以外は formula_14
 各頂点 formula_11 に対し、formula_16 「無し」
 formula_1 に formula_18 の頂点を全て追加
 // 本計算
 while ( formula_1 が空ではない )
 formula_20 から formula_21 が最小である頂点を取り除き取り出す
 for each ( formula_2 からの辺がある各頂点 formula_11 )
 if ( formula_24 )
 formula_25
 formula_26
「formula_20 から formula_21 が最小である頂点を取り除き取り出す」の部分は、エドガー・ダイクストラによるオリジナルでは単純に集合内を探索するアルゴリズムだが、その操作の計算量を減らすために、formula_1 として、優先度付きキュー（フィボナッチヒープ）を用いることが行われる。ただしその場合、formula_1 に関する部分を少し変更する必要がある。下記は優先度付きキューを用いたことを想定し上記を書き換えたダイクストラ法の擬似コードである。
 // 初期化 
 for ( formula_31 )
 formula_12 ならば formula_13 、それ以外は formula_14
 formula_35 「無し」
 formula_36
 // 本計算
 while ( formula_1 が空集合ではない )
 formula_20 から formula_21 が最小である頂点 formula_2 を取り除き取り出す
 for each ( formula_2 からの辺がある各 formula_11 )
 formula_43
 if ( formula_44 )
 formula_45
 formula_46
 formula_47
「for each ( formula_2 からの辺がある各頂点 formula_11 )」の部分は「for each ( formula_2 からの辺がある各頂点 formula_51 )」でも同じ結果が得られるが、 formula_52 ではあるものの、逆に計算量が増えてしまう場合もあり得ることに注意。
GCC の C++ の priority_queue はを使用しているため、これを使うとフィボナッチヒープと同等の計算量のコードが簡単に実装できる。
計算量.
計算量は以下の通り。
優先度付きキューを使用した場合の計算量としては、以下の合算である。下記説明は上記擬似コードに基づき、ループ回数も考慮に入れている。
アルゴリズムの解説.
概略.
話を簡単にするため、formula_6 の各頂点 formula_69 に対し、formula_3 と formula_71 を結ぶ辺は最大一つしかないとする。
formula_3 と formula_71 を結ぶ辺があれば、その辺を formula_74 と書く。
最短経路問題は、ビー玉と紐を用いて解くことができる。
まずビー玉を頂点、紐を辺にするグラフを工作する。
グラフを板の上に置き、スタートの頂点にあたるビー玉だけをつまむ。
グラフが置かれている板を取り除くと、グラフは自由落下を始めるが、
スタートにあたるビー玉を持っているので、スタート地点から近いビー玉から順に落下が止まる。
ゴールにあたるビー玉が止まったとき、ゴールにあたるビー玉はスタートにあたるビー玉まで紐で一直線で結ばれている。
この直線が最短経路である。
落下が止まった頂点 formula_3 に対し、formula_3 を支えている頂点 formula_71 が存在する。
formula_71 を formula_3 の「直前の頂点」と呼ぶことにする。
以下簡単のため、直前の頂点は1つしかないと仮定して話を進めるが、
一般の場合も同様である。
ダイクストラのアルゴリズムは、上述の解法をコンピュータ上でシミュレートしたものである。
グラフ formula_6、スタートとなる頂点 formula_7、および各辺 formula_82 の長さ formula_83 が入力として与えられると、
このアルゴリズムは上述の解法をシミュレートし、「落下」が停止した頂点から順に、その頂点の直前の頂点が何であるかを出力する。
ゴールとなる頂点の「落下」が停止したところで、ダイクストラのアルゴリズムを止めれば、
あとはゴールから順に、直前の頂点、さらにその直前の頂点とたどっていくことで、
ゴールとスタートをつなぐ最短経路(の一つ)を求めることができる。
詳細.
以上の考察から分かるように、ダイクストラ法では「次に落下が停止する頂点」（とその直前の頂点）を求めることが重要である。
そこでこれらを効率的に求める方法を説明する。
現時点で「落下」が停止している頂点の集合をHとし、
各頂点 formula_11 に対して formula_85 内での formula_3 と formula_7 との最短距離を formula_4 とする（formula_85 内で formula_7 から formula_3 に到達できないときは formula_92 とする）。
さらに、formula_93 に隣接している頂点の集合を formula_94 とする。
ここで頂点 formula_3 が formula_93 に隣接しているとは、formula_3 と formula_93 内のいずれか頂点を結ぶ辺が存在することを指す。
次に落下が停止する頂点を formula_2 とし、formula_2 の直前の頂点を formula_101 とすると、
以下が成立することが分かる。
そこでダイクストラ法では、「次に落下が停止する頂点」(とその直前の頂点)を効率的に求めるために、
以下の3種類のデータを管理する。
ダイクストラ法では、formula_94 内で formula_21 が最小になる頂点 formula_2（formula_122次に落下が停止する頂点）を求めて formula_2 を出力し、それにあわせて管理しているデータを更新し、そしてさらに次に落下が停止する頂点を求める、という操作を繰り返す。
そこで最後に、ダイクストラ法が管理しているデータを更新する方法を述べる。
formula_94 内で formula_21 が最小になる頂点 formula_2（formula_122次に落下する頂点）が求まったら、まず formula_2 を formula_93 に追加する。それにあわせて formula_94 から formula_2 を除去し、formula_2 に隣接していてかつ formula_93 に属さない頂点を formula_94 に加える。
formula_2 を formula_93 に追加した結果「formula_85 内での formula_7 から formula_3 への最短距離」である formula_4 が変化するのは、
formula_2 と formula_3 とを結ぶ辺がある場合に限られる。
formula_2 を formula_93 に追加後の「formula_85 内での formula_7 から formula_3 への最短距離」は次のいずれかと一致する。
(a)の長さは formula_2 を formula_93 に追加する前の段階での formula_4 に一致し、
一方(b)の長さは formula_2 を formula_93 に追加する前の段階での formula_21 に formula_164 を加えた長さである。
以上の考察より、formula_4 および formula_118 を次のように更新すればよいことがわかる：