ダイクストラ法

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

ダイクストラ法はグラフ理論における最短経路問題を解くためのアルゴリズムである。

概要

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

アルゴリズムの概要

簡単の為、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に更新。
  • そうでなければ何もしない。

擬似コード

ダイクストラのアルゴリズムは以下の通りである：

• グラフG = (V,E)、スタートとなる頂点s、および各辺eの長さlength(e)が入力として受け取る。
• $H \leftarrow \emptyset$。
• $d(s) \leftarrow 0$。s以外の各$v \in V$に対し、$d(v) \leftarrow \infty$。
• 各$v \in V$に対し、w_v ← 「無し」。

• while ($V \setminus H \neq \emptyset$) do
  • $u \leftarrow d(v)$が最小となる頂点
  • (u,w_u)を出力
  • $H \leftarrow H \cup \{u\}$
    • for(uからの辺がある各$v \in V\setminus H$) do
      • if $(d(v) > d(u) + \text{length}(u,v))\{ d(v) \leftarrow d(u) + \text{length}(u,v), w_v \leftarrow u\}$。
    • done
• done

関連項目

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

参考文献

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