ダイクストラ法

提供: miniwiki
移動先:案内、検索
最短経路問題 > ダイクストラ法
ファイル:Dijkstra Animation.gif
ダイクストラ法の動作のアニメーション

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

概要

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

擬似コード

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

グラフ [math]G=(V,E)[/math] 、スタートとなる頂点 [math]s[/math] 、および [math]u[/math] から [math]v[/math] への辺の長さ [math]\text{length}(u, v)[/math] を入力として受け取る

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

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

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

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

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

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

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

計算量

計算量は以下の通り。

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

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

アルゴリズムの解説

概略

話を簡単にするため、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の直前の頂点をwu∈Hとすると、 以下が成立することが分かる。

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

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

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

ダイクストラ法では、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)およびwvを次のように更新すればよいことがわかる：

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

脚注

  1. ↑ 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. 
  2. ↑ コルテ & フィーゲン 2009, アルゴリズム 7.1.
  3. ↑ Priority-Queues
  4. ↑ 4.0 4.1 コルテ & フィーゲン 2009, p. 185.

参考文献

関連項目

テンプレート:アルゴリズム



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=ダイクストラ法&oldid=112349」から取得