Loading AI tools
ウィキペディアから
ダイクストラ法(だいくすとらほう、英: Dijkstra's algorithm)はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。
ダイクストラ法は、1959年エドガー・ダイクストラによって考案された。 応用範囲は広くOSPFなどのインターネットルーティングプロトコルや、カーナビの経路探索や鉄道の経路案内においても利用されている。
ほかのアルゴリズムとして、
ダイクストラ法の擬似コードは以下の通りである[2]。始点(スタート)から全てのグラフの頂点への最短経路を求める。
// 初期化 各頂点 に対し、 ならば 、それ以外は 各頂点 に対し、 「無し」 に の頂点を全て追加 // 本計算 while ( が空ではない ) から が最小である頂点を取り除き取り出す for each ( からの辺がある各頂点 ) if ( )
なお、「 から が最小である頂点を取り除き取り出す」の部分は、エドガー・ダイクストラによるオリジナルのアルゴリズム通りに、集合内の単純探索を想定している。
「 の中の が最小な頂点」の部分は、始点から最短経路の長さでへ到達したこととなる。以降はこのに関するの値は更新されることはない。またしたがって、「for each ( からの辺がある各頂点 )」の部分は、「for each ( からの辺がある各頂点 )」へ変更しても同等となる。
もしも集合 が、の値に基づく優先度付きキューの機能を併せ持っているならば、最小に当たる頂点を探索し取り出す計算量を単純探索に比べて減らせる可能性がある。その場合、擬似コードも へ値を代入する操作を明示的に書くと分かりやすい。
// 初期化 for ( ) ならば 、それ以外は 「無し」 // 本計算 while ( が空集合ではない ) から が最小である頂点 を取り除き取り出す for each ( からの辺がある各 ) if ( )
「 から が最小である頂点 を取り除き取り出す」においては、 への再訪は起きないことはオリジナルと同様である(なぜならば「」の部分は代入であり、 の中に の重複を起こさないためである[注釈 1])。
「for each ( からの辺がある各頂点 )」の部分は「for each ( からの辺がある各頂点 )」でも同じ結果が得られるが、 ではあるものの、逆に計算量が増えてしまう場合もあり得ることに注意。
計算量を低減できる優先度付きキューの例としてフィボナッチヒープがある。また、C++ではg++拡張の__gnu_pbds::priority_queueはデフォルトでペアリングヒープを使用しているため[3]、これを使うとフィボナッチヒープと同等の計算量のコードが簡単に実装できる。[要検証]
計算量は以下の通り。
優先度付きキューを使用した場合の計算量としては、以下の合算である。下記説明は上記擬似コードに基づき、ループ回数も考慮に入れている。
話を簡単にするため、 の各頂点 に対し、 と を結ぶ辺は最大一つしかないとする。 と を結ぶ辺があれば、その辺を と書く。
最短経路問題は、ビー玉と紐を用いて解くことができる。 まずビー玉を頂点、紐を辺にするグラフを工作する。 グラフを板の上に置き、スタートの頂点にあたるビー玉だけをつまむ。 グラフが置かれている板を取り除くと、グラフは自由落下を始めるが、 スタートにあたるビー玉を持っているので、スタート地点から近いビー玉から順に落下が止まる。 ゴールにあたるビー玉が止まったとき、ゴールにあたるビー玉はスタートにあたるビー玉まで紐で一直線で結ばれている。 この直線が最短経路である。
落下が止まった頂点 に対し、 を支えている頂点 が存在する。 を の「直前の頂点」と呼ぶことにする。 以下簡単のため、直前の頂点は1つしかないと仮定して話を進めるが、 一般の場合も同様である。
ダイクストラのアルゴリズムは、上述の解法をコンピュータ上でシミュレートしたものである。 グラフ 、スタートとなる頂点 、および各辺 の長さ が入力として与えられると、 このアルゴリズムは上述の解法をシミュレートし、「落下」が停止した頂点から順に、その頂点の直前の頂点が何であるかを出力する。 ゴールとなる頂点の「落下」が停止したところで、ダイクストラのアルゴリズムを止めれば、 あとはゴールから順に、直前の頂点、さらにその直前の頂点とたどっていくことで、 ゴールとスタートをつなぐ最短経路(の一つ)を求めることができる。
以上の考察から分かるように、ダイクストラ法では「次に落下が停止する頂点」(とその直前の頂点)を求めることが重要である。 そこでこれらを効率的に求める方法を説明する。
現時点で「落下」が停止している頂点の集合をHとし、 各頂点 に対して 内での と との最短距離を とする( 内で から に到達できないときは とする)。 さらに、 に隣接している頂点の集合を とする。 ここで頂点 が に隣接しているとは、 と 内のいずれか頂点を結ぶ辺が存在することを指す。
次に落下が停止する頂点を とし、 の直前の頂点を とすると、 以下が成立することが分かる。
そこでダイクストラ法では、「次に落下が停止する頂点」(とその直前の頂点)を効率的に求めるために、 以下の3種類のデータを管理する。
ダイクストラ法では、 内で が最小になる頂点 (次に落下が停止する頂点)を求めて を出力し、それにあわせて管理しているデータを更新し、そしてさらに次に落下が停止する頂点を求める、という操作を繰り返す。
そこで最後に、ダイクストラ法が管理しているデータを更新する方法を述べる。
内で が最小になる頂点 (次に落下する頂点)が求まったら、まず を に追加する。それにあわせて から を除去し、 に隣接していてかつ に属さない頂点を に加える。
を に追加した結果「 内での から への最短距離」である が変化するのは、 と とを結ぶ辺がある場合に限られる。
を に追加後の「 内での から への最短距離」は次のいずれかと一致する。
(a)の長さは を に追加する前の段階での に一致し、 一方(b)の長さは を に追加する前の段階での に を加えた長さである。
以上の考察より、 および を次のように更新すればよいことがわかる:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.