ダイクストラ法

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

ダイクストラ法の動作のアニメーション

ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。辺の重みに負数を含む場合はベルマン-フォード法などが使える。辺の重みが全て同一の非負数の場合は幅優先探索が速く、線形時間で最短路を計算可能である。また、無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズムによって線形時間での計算が可能であるが、実用性はあまり高くない。

概要

ダイクストラ法はグラフ上の2頂点間の最短経路を求めるアルゴリズムで、1959年エドガー・ダイクストラによって考案された。 応用範囲は広くOSPFなどのインターネットルーティングプロトコルや、カーナビの経路探索や鉄道の経路案内においても利用されている。 なお最短経路長の推定値を事前に知っているときは、ダイクストラ法の改良版であるA*アルゴリズムを用いて、より効率的に最短経路を求めることができる。

擬似コード

ダイクストラ法の擬似コードは以下の通りである。 $Q$ は頂点の集合（もしくは優先度付きキュー）。 $u$, $v$ は頂点。 $d(v)$ はスタートとなる頂点からの最短経路の長さ。 $\operatorname {prev} (v)$ は最短経路をたどる際の前の頂点。

グラフ $G=(V,E)$ 、スタートとなる頂点 $s$ 、および $u$ から $v$ への辺の長さ ${\text{length}}(u,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$ )
       if ( $d(v)>d(u)+{\text{length}}(u,v)$ )
           $d(v)\leftarrow d(u)+{\text{length}}(u,v)$
           $\operatorname {prev} (v)\leftarrow u$

「$u\leftarrow Q$ から $d(u)$ が最小である頂点を取り除く」の部分は、オリジナルは単純に集合内を探索するアルゴリズムだが、$Q$ を優先度付きキュー（フィボナッチヒープ）にすることで、より計算量が減る。ただしその場合、$Q$ に関する部分を少し変更する必要がある。下記は優先度付きキューを用いたことを想定し上記を書き換えたダイクストラ法の擬似コードである。

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

// 本計算
while ( $Q$ が空集合ではない )
  $Q$ から $Q(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$

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

GCC の C++ の priority_queue はペアリングヒープを使用しているため、これを使うとフィボナッチヒープと同等の計算量のコードが簡単に実装できる。

計算量

計算量は以下の通り。

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

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

• 「$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$ に更新。
  • そうでなければ何もしない。

参考文献

• 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。 

関連項目

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