ダイクストラ法

ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。

ダイクストラ法は、1959年エドガー・ダイクストラによって考案された。 応用範囲は広くOSPFなどのインターネットルーティングプロトコルや、カーナビの経路探索や鉄道の経路案内においても利用されている。

ほかのアルゴリズムとして、

• 最短経路長の推定値を事前に知っているときは、ダイクストラ法の改良版であるA*アルゴリズムを用いて、より効率的に最短経路を求めることができる。
• 辺の重みが全て同一の非負数の場合は幅優先探索がより速く、線形時間で最短路を計算可能である。
• 無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズム^[1]によって線形時間での計算が可能であるが、実用性はあまり高くない^[要出典]。
• 辺の重みに負数を含む場合はベルマン-フォード法がある。

ダイクストラ法の擬似コードは以下の通りである^[2]。始点（スタート）から全てのグラフの頂点への最短経路を求める。

• ${\displaystyle Q}$ は頂点の集合。 ${\displaystyle u}$, ${\displaystyle v}$ は頂点。
• グラフ ${\displaystyle G=(V,E)}$ 、始点 ${\displaystyle s}$ 、および ${\displaystyle u}$ から ${\displaystyle v}$ への辺の長さ ${\displaystyle {\text{length}}(u,v)}$ を入力として受け取る。
• 計算終了時に、${\displaystyle d(v)}$ は始点 ${\displaystyle s}$からの最短経路の長さ。 ${\displaystyle \operatorname {prev} (v)}$ は最短経路をたどる際の前の頂点。

// 初期化 
各頂点 ${\displaystyle v\in V}$ に対し、${\displaystyle d(v)\leftarrow (v=s}$ ならば ${\displaystyle 0}$ 、それ以外は ${\displaystyle \infty )}$
各頂点 ${\displaystyle v\in V}$ に対し、${\displaystyle \operatorname {prev} (v)\leftarrow }$ 「無し」
${\displaystyle Q}$ に ${\displaystyle V}$ の頂点を全て追加

// 本計算
while ( ${\displaystyle Q}$ が空ではない )
   ${\displaystyle u\leftarrow Q}$ から ${\displaystyle d(u)}$ が最小である頂点を取り除き取り出す
   for each ( ${\displaystyle u}$ からの辺がある各頂点 ${\displaystyle v\in V}$ )
       ${\displaystyle alt\leftarrow d(u)+{\text{length}}(u,v)}$
       if ( ${\displaystyle d(v)>alt}$ )
           ${\displaystyle d(v)\leftarrow alt}$
           ${\displaystyle \operatorname {prev} (v)\leftarrow u}$

なお、「${\displaystyle u\leftarrow Q}$ から ${\displaystyle d(u)}$ が最小である頂点を取り除き取り出す」の部分は、エドガー・ダイクストラによるオリジナルのアルゴリズム通りに、集合内の単純探索を想定している。

「${\displaystyle Q}$ の中の ${\displaystyle d(u)}$ が最小な頂点${\displaystyle u}$」の部分は、始点から最短経路の長さ${\displaystyle d(u)}$で${\displaystyle u}$へ到達したこととなる。以降はこの${\displaystyle u}$に関する${\displaystyle d(u)}$の値は更新されることはない。またしたがって、「for each ( ${\displaystyle u}$ からの辺がある各頂点 ${\displaystyle v\in V}$ )」の部分は、「for each ( ${\displaystyle u}$ からの辺がある各頂点 ${\displaystyle v\in Q}$ )」へ変更しても同等となる。

もしも集合 ${\displaystyle Q}$ が、${\displaystyle d(u)}$の値に基づく優先度付きキューの機能を併せ持っているならば、最小に当たる頂点を探索し取り出す計算量を単純探索に比べて減らせる可能性がある。その場合、擬似コードも ${\displaystyle Q(v)}$ へ値を代入する操作を明示的に書くと分かりやすい。

// 初期化 
for ( ${\displaystyle v\leftarrow V}$ )
    ${\displaystyle d(v)\leftarrow (v=s}$ ならば ${\displaystyle 0}$ 、それ以外は ${\displaystyle \infty )}$
    ${\displaystyle prev(v)\leftarrow }$ 「無し」
    ${\displaystyle Q(v)\leftarrow d(v)}$

// 本計算
while ( ${\displaystyle Q}$ が空集合ではない )
  ${\displaystyle u\leftarrow Q}$ から ${\displaystyle d(u)}$ が最小である頂点 ${\displaystyle u}$ を取り除き取り出す
   for each ( ${\displaystyle u}$ からの辺がある各 ${\displaystyle v\in V}$ )
       ${\displaystyle alt\leftarrow d(u)+{\text{length}}(u,v)}$
       if ( ${\displaystyle d(v)>alt}$ )
           ${\displaystyle d(v)\leftarrow alt}$
           ${\displaystyle prev(v)\leftarrow u}$
           ${\displaystyle Q(v)\leftarrow alt}$

「${\displaystyle u\leftarrow Q}$ から ${\displaystyle d(u)}$ が最小である頂点 ${\displaystyle u}$ を取り除き取り出す」においては、${\displaystyle u}$ への再訪は起きないことはオリジナルと同様である（なぜならば「${\displaystyle Q(v)\leftarrow alt}$」の部分は代入であり、${\displaystyle Q}$ の中に ${\displaystyle v}$ の重複を起こさないためである^{[注釈 1]}）。

「for each ( ${\displaystyle u}$ からの辺がある各頂点 ${\displaystyle v\in V}$ )」の部分は「for each ( ${\displaystyle u}$ からの辺がある各頂点 ${\displaystyle v\in Q}$ )」でも同じ結果が得られるが、 ${\displaystyle Q\subset V}$ ではあるものの、逆に計算量が増えてしまう場合もあり得ることに注意。

計算量を低減できる優先度付きキューの例としてフィボナッチヒープがある。また、C++ではg++拡張の__gnu_pbds::priority_queueはデフォルトでペアリングヒープを使用しているため^[3]、これを使うとフィボナッチヒープと同等の計算量のコードが簡単に実装できる。^{[要検証 – ノート]}

計算量は以下の通り。

• オリジナル : ${\displaystyle O(V^{2})}$^[4]
• 優先度付きキュー（二分ヒープ）: ${\displaystyle O((E+V)\log {V})}$
• 優先度付きキュー（フィボナッチヒープ）: ${\displaystyle O(E+V\log {V})}$^[4]

優先度付きキューを使用した場合の計算量としては、以下の合算である。下記説明は上記擬似コードに基づき、ループ回数も考慮に入れている。

• 「${\displaystyle Q\leftarrow V}$」：二分ヒープもフィボナッチヒープも ${\displaystyle O(V)}$ 。ただし、二分ヒープは追加を V 回繰り返す実装にすると ${\displaystyle O(V\log V)}$ 。
• 「${\displaystyle u\leftarrow d(u)}$ が最小である頂点 ${\displaystyle u\in Q}$」：二分ヒープもフィボナッチヒープも ${\displaystyle O(V)}$
• 「${\displaystyle Q}$ から ${\displaystyle u}$ を取り除き取り出す」：二分ヒープもフィボナッチヒープも ${\displaystyle O(V\log V)}$
• 「${\displaystyle d(v)\leftarrow d(u)+{\text{length}}(u,v)}$」：二分ヒープは ${\displaystyle O(E\log V)}$ 、フィボナッチヒープは ${\displaystyle O(E)}$

話を簡単にするため、${\displaystyle G=(V,E)}$ の各頂点 ${\displaystyle v,w\in V}$ に対し、${\displaystyle v}$ と ${\displaystyle w}$ を結ぶ辺は最大一つしかないとする。 ${\displaystyle v}$ と ${\displaystyle w}$ を結ぶ辺があれば、その辺を ${\displaystyle (v,w)}$ と書く。

最短経路問題は、ビー玉と紐を用いて解くことができる。 まずビー玉を頂点、紐を辺にするグラフを工作する。 グラフを板の上に置き、スタートの頂点にあたるビー玉だけをつまむ。 グラフが置かれている板を取り除くと、グラフは自由落下を始めるが、 スタートにあたるビー玉を持っているので、スタート地点から近いビー玉から順に落下が止まる。 ゴールにあたるビー玉が止まったとき、ゴールにあたるビー玉はスタートにあたるビー玉まで紐で一直線で結ばれている。 この直線が最短経路である。

落下が止まった頂点 ${\displaystyle v}$ に対し、${\displaystyle v}$ を支えている頂点 ${\displaystyle w}$ が存在する。 ${\displaystyle w}$ を ${\displaystyle v}$ の「直前の頂点」と呼ぶことにする。 以下簡単のため、直前の頂点は1つしかないと仮定して話を進めるが、 一般の場合も同様である。

ダイクストラのアルゴリズムは、上述の解法をコンピュータ上でシミュレートしたものである。 グラフ ${\displaystyle G=(V,E)}$、スタートとなる頂点 ${\displaystyle s}$、および各辺 ${\displaystyle e}$ の長さ ${\displaystyle {\text{length}}(e)}$ が入力として与えられると、 このアルゴリズムは上述の解法をシミュレートし、「落下」が停止した頂点から順に、その頂点の直前の頂点が何であるかを出力する。 ゴールとなる頂点の「落下」が停止したところで、ダイクストラのアルゴリズムを止めれば、 あとはゴールから順に、直前の頂点、さらにその直前の頂点とたどっていくことで、 ゴールとスタートをつなぐ最短経路(の一つ)を求めることができる。

以上の考察から分かるように、ダイクストラ法では「次に落下が停止する頂点」（とその直前の頂点）を求めることが重要である。 そこでこれらを効率的に求める方法を説明する。

現時点で「落下」が停止している頂点の集合をHとし、 各頂点 ${\displaystyle v\in V}$ に対して ${\displaystyle H\cup {v}}$ 内での ${\displaystyle v}$ と ${\displaystyle s}$ との最短距離を ${\displaystyle d(v)}$ とする（${\displaystyle H\cup {v}}$ 内で ${\displaystyle s}$ から ${\displaystyle v}$ に到達できないときは ${\displaystyle d(v)=\inf }$ とする）。 さらに、${\displaystyle H}$ に隣接している頂点の集合を ${\displaystyle A}$ とする。 ここで頂点 ${\displaystyle v}$ が ${\displaystyle H}$ に隣接しているとは、${\displaystyle v}$ と ${\displaystyle H}$ 内のいずれか頂点を結ぶ辺が存在することを指す。

次に落下が停止する頂点を ${\displaystyle u}$ とし、${\displaystyle u}$ の直前の頂点を ${\displaystyle w_{u}\in H}$ とすると、 以下が成立することが分かる。

• ${\displaystyle u}$ は ${\displaystyle A}$ に属し、しかも ${\displaystyle A}$ 内で ${\displaystyle d(u)}$ が最小になる頂点である。
• ${\displaystyle s}$ から ${\displaystyle u}$ への最短経路は ${\displaystyle w_{u}\in H}$ を通る。

そこでダイクストラ法では、「次に落下が停止する頂点」(とその直前の頂点)を効率的に求めるために、 以下の3種類のデータを管理する。

• 集合 ${\displaystyle H}$ と集合 ${\displaystyle A}$
• 各頂点 ${\displaystyle v\in V}$ に対して ${\displaystyle H\cup {v}}$ 内での ${\displaystyle s}$ から ${\displaystyle v}$ への最短距離 ${\displaystyle d(v)}$。
• 各 ${\displaystyle v\in A}$ に対し、${\displaystyle v}$ の直前の頂点 ${\displaystyle w_{v}}$

ダイクストラ法では、${\displaystyle A}$ 内で ${\displaystyle d(u)}$ が最小になる頂点 ${\displaystyle u}$（${\displaystyle =}$次に落下が停止する頂点）を求めて ${\displaystyle u}$ を出力し、それにあわせて管理しているデータを更新し、そしてさらに次に落下が停止する頂点を求める、という操作を繰り返す。

そこで最後に、ダイクストラ法が管理しているデータを更新する方法を述べる。

${\displaystyle A}$ 内で ${\displaystyle d(u)}$ が最小になる頂点 ${\displaystyle u}$（${\displaystyle =}$次に落下する頂点）が求まったら、まず ${\displaystyle u}$ を ${\displaystyle H}$ に追加する。それにあわせて ${\displaystyle A}$ から ${\displaystyle u}$ を除去し、${\displaystyle u}$ に隣接していてかつ ${\displaystyle H}$ に属さない頂点を ${\displaystyle A}$ に加える。

${\displaystyle u}$ を ${\displaystyle H}$ に追加した結果「${\displaystyle H\cup {v}}$ 内での ${\displaystyle s}$ から ${\displaystyle v}$ への最短距離」である ${\displaystyle d(v)}$ が変化するのは、 ${\displaystyle u}$ と ${\displaystyle v}$ とを結ぶ辺がある場合に限られる。

${\displaystyle u}$ を ${\displaystyle H}$ に追加後の「${\displaystyle H\cup {v}}$ 内での ${\displaystyle s}$ から ${\displaystyle v}$ への最短距離」は次のいずれかと一致する。

• (a) ${\displaystyle u}$ を ${\displaystyle H}$ に追加する前の段階での ${\displaystyle s}$ から ${\displaystyle v}$ への最短経路
• (b) ${\displaystyle u}$ を ${\displaystyle H}$ に追加する前の段階での ${\displaystyle s}$ から ${\displaystyle u}$ への最短経路を通った後で ${\displaystyle u}$ と ${\displaystyle v}$ を結ぶ辺を通るという経路

(a)の長さは ${\displaystyle u}$ を ${\displaystyle H}$ に追加する前の段階での ${\displaystyle d(v)}$ に一致し、 一方(b)の長さは ${\displaystyle u}$ を ${\displaystyle H}$ に追加する前の段階での ${\displaystyle d(u)}$ に ${\displaystyle {\text{length}}(u,v)}$ を加えた長さである。

以上の考察より、${\displaystyle d(v)}$ および ${\displaystyle w_{v}}$ を次のように更新すればよいことがわかる：

• ${\displaystyle u}$ から ${\displaystyle v}$ への辺が存在する各 ${\displaystyle v}$ に対し、
  • ${\displaystyle d(v)>d(u)+{\text{length}}(u,v)}$ なら、${\displaystyle d(v)}$ を「${\displaystyle d(u)+{\text{length}}(u,v)}$」に更新し、さらに${\displaystyle w_{v}}$を ${\displaystyle u}$ に更新。
  • そうでなければ何もしない。

1. ^ もしも重複を許す実装を行なうなど再訪が生じる場合には計算量が増える。しかし${\displaystyle d(u)}$を${\displaystyle Q}$ の中から取り出した値と比較し等しくない場合は再訪と判定でき防ぐことができる。

• Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. In Numerische Mathematik, 1 (1959), S. 269 ～ 271.
• コルテ, B.、フィーゲン, J.『組合せ最適化 : 理論とアルゴリズム』（第2版）シュプリンガー・ジャパン、2009年、184–185頁。ISBN 978-4431100218。https://books.google.co.jp/books?id=7OfUJPqwyKwC&pg=PA184。 

• 最良優先探索
• A*
• 均一コスト探索
• 最短経路問題
• 動的計画法
• ベルマン-フォード法

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤンの楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂単体法（英語版） 十文字法（英語版） レムケの主ピボット操作法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 分枝カット法) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）