ダイクストラ法

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

ダイクストラ法はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くためのアルゴリズムである。辺の重みに負数を含む場合はベルマン-フォード法などが使える。辺の重みが全て同一の非負数の場合は幅優先探索の方が速い。

概要

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

擬似コード

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

グラフ $G=(V,E)$ 、スタートとなる頂点 $s$ 、および各辺 $e$ の長さ $\text{length}(e)$ を入力として受け取る

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

// 本計算
while ( $Q$ が空集合ではない )
   $u \leftarrow Q(u)$ を最小とするような頂点 $u$
   $Q$ から $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)$
           $prev(v) \leftarrow u$
           $Q(v) \leftarrow d(u) + \text{length}(u,v)$

「$u \leftarrow d(u)$ が最小である頂点 $u \in Q$」の部分は、オリジナルは単純に集合内を探索するアルゴリズムだが、優先度つきキュー（フィボナッチヒープ）を使う事により、より計算量が減る。GCC の C++ の priority_queue はペアリングヒープを使用しているため、これを使うとフィボナッチヒープと同等の計算量のコードが簡単に実装できる。

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

計算量

計算量は以下の通り。

• オリジナル - $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∈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_u∈Hとすると、 以下が成立する事が分かる。

• uはAに属し、しかもA内でd(u)が最小になる頂点である。
• sからuへの最短経路はw_u∈Hを通る。

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

• 集合Hと集合A
• 各頂点v∈Vに対してH∪{v}内でのsからvへの最短距離d(v)。
• 各v∈Aに対し、vの直前の頂点w_v

ダイクストラ法では、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に追加する前の段階でのsからvへの最短経路
• (b) uをHに追加する前の段階でのsからuへの最短経路を通った後でuとvを結ぶ辺を通るという経路

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

以上の考察より、d(v)およびw_vを次のように更新すればよい事が分かる：

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

関連項目

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

参考文献

• Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. In Numerische Mathematik, 1 (1959), S. 269 ～ 271.