ダイクストラ法

最短経路問題 > ダイクストラ法

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

概要

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

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

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

擬似コード

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

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

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

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

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

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

優先度付きキューの利用

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

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

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

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

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

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

計算量

計算量は以下の通り。

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

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

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

アルゴリズムの解説

概略

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

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

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

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

詳細

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

注釈

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

引用

^ Thorup, Mikkel (1999). “Undirected single-source shortest paths with positive integer weights in linear time”. journal of the ACM 46 (3): 362-394. doi:10.1145/316542.316548.
^ コルテ & フィーゲン 2009, アルゴリズム 7.1.
^ Priority-Queues
^ ^a ^b コルテ & フィーゲン 2009, p. 185.

参考文献

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.com/books?id=7OfUJPqwyKwC&pg=PA184。