ダイクストラ法のソースを表示

{{pathnav|最短経路問題|frame=1}}
[[ファイル:Dijkstra_Animation.gif|thumb|right|300px|ダイクストラ法の動作のアニメーション]]
'''ダイクストラ法'''（だいくすとらほう、{{lang-en-short|Dijkstra's algorithm}}）は[[グラフ理論]]における辺の重みが非負数の場合の単一始点[[最短経路問題]]を解くための[[最良優先探索]]による[[アルゴリズム]]である。

== 概要 ==
ダイクストラ法は、1959年[[エドガー・ダイクストラ]]によって考案された。
応用範囲は広く[[オープン・ショーテスト・パス・ファースト|OSPF]]などの[[インターネット]][[ルーティングプロトコル]]や、[[カーナビゲーション|カーナビ]]の経路探索や鉄道の経路案内においても利用されている。

ほかのアルゴリズムとして、
* 最短経路長の推定値を事前に知っているときは、ダイクストラ法の改良版である[[A*|A*アルゴリズム]]を用いて、より効率的に最短経路を求めることができる。
* 辺の重みが全て同一の非負数の場合は[[幅優先探索]]がより速く、線形時間で最短路を計算可能である。
* 無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズム<ref>{{cite journal
|first1=Mikkel
|last1=Thorup
|title=Undirected single-source shortest paths with positive integer weights in linear time
|journal=journal of the ACM
|volume=46
|issue=3
|pages=362-394
|year=1999
|doi=10.1145/316542.316548}}</ref>によって線形時間での計算が可能であるが、実用性はあまり高くない{{要出典|date=2021年1月}}。
* 辺の重みに負数を含む場合は[[ベルマン-フォード法]]がある。

== 擬似コード ==
ダイクストラ法の擬似コードは以下の通りである{{sfn|コルテ|フィーゲン|2009|loc=アルゴリズム 7.1}}。始点（スタート）から全てのグラフの頂点への最短経路を求める。
* <math>Q</math> は頂点の集合。 <math>u</math>, <math>v</math> は頂点。 
* グラフ <math>G=(V,E)</math> 、始点 <math>s</math> 、および <math>u</math> から <math>v</math> への辺の長さ <math>\text{length}(u, v)</math> を入力として受け取る。
* 計算終了時に、<math>d(v)</math> は始点 <math>s</math>からの最短経路の長さ。 <math>\operatorname{prev}(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> )
        <math>alt \leftarrow d(u) + \text{length}(u,v)</math>
        if ( <math>d(v) > alt</math> )
            <math>d(v) \leftarrow alt</math>
            <math>\operatorname{prev}(v) \leftarrow u</math>

なお、「<math>u \leftarrow Q</math> から <math>d(u)</math> が最小である頂点を取り除き取り出す」の部分は、[[エドガー・ダイクストラ]]によるオリジナルのアルゴリズム通りに、集合内の単純探索を想定している。

「<math>Q</math> の中の <math>d(u)</math> が最小な頂点<math>u</math>」の部分は、始点から最短経路の長さ<math>d(u)</math>で<math>u</math>へ到達したこととなる。以降はこの<math>u</math>に関する<math>d(u)</math>の値は更新されることはない。またしたがって、「for each ( <math>u</math> からの辺がある各頂点 <math>v \in V</math> )」の部分は、「for each ( <math>u</math> からの辺がある各頂点 <math>v \in Q</math> )」へ変更しても同等となる。

===優先度付きキューの利用===
もしも集合 <math>Q</math> が、<math>d(u)</math>の値に基づく[[優先度付きキュー]]の機能を併せ持っているならば、最小に当たる頂点を探索し取り出す[[計算量]]を単純探索に比べて減らせる可能性がある。<!--下記の擬似コードには何も変更が見当たらない。-->その場合、擬似コードも <math>Q(v)</math> へ値を代入する操作を明示的に書くと分かりやすい。

 // 初期化 
 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>u \leftarrow Q</math> から <math>d(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) > alt</math> )
            <math>d(v) \leftarrow alt</math>
            <math>prev(v) \leftarrow u</math>
            <math>Q(v) \leftarrow alt</math>

「<math>u \leftarrow Q</math> から <math>d(u)</math> が最小である頂点 <math>u</math> を取り除き取り出す」においては、<math>u</math> への再訪は起きないことはオリジナルと同様である（なぜならば「<math>Q(v) \leftarrow alt</math>」の部分は代入であり、<math>Q</math> の中に <math>v</math> の重複を起こさないためである<ref group="注釈">もしも重複を許す実装を行なうなど再訪が生じる場合には計算量が増える。しかし<math>d(u)</math>を<math>Q</math> の中から取り出した値と比較し等しくない場合は再訪と判定でき防ぐことができる。</ref>）。

「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> ではあるものの、逆に計算量が増えてしまう場合もあり得ることに注意。

計算量を低減できる[[優先度付きキュー]]の例として[[フィボナッチヒープ]]がある。また、C++ではg++拡張の__gnu_pbds::priority_queueはデフォルトで[[:en:Pairing heap|ペアリングヒープ]]を使用しているため<ref>[http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/pq_design.html Priority-Queues]</ref>、{{要検証範囲|これを使うとフィボナッチヒープと同等の計算量のコードが簡単に実装できる。|date=2024年4月}}

== 計算量 ==
[[計算量]]は以下の通り。
* オリジナル : <math>O(V^2)</math>{{sfn|コルテ|フィーゲン|2009|p=185}}
* [[優先度付きキュー]]（[[二分ヒープ]]）: <math>O((E+V) \log{V})</math>
* 優先度付きキュー（[[フィボナッチヒープ]]）: <math>O(E+V \log{V})</math>{{sfn|コルテ|フィーゲン|2009|p=185}}

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

== アルゴリズムの解説 ==
=== 概略 ===
話を簡単にするため、<math>G=(V,E)</math> の各頂点 <math>v,w \in V</math> に対し、<math>v</math> と <math>w</math> を結ぶ辺は最大一つしかないとする。
<math>v</math> と <math>w</math> を結ぶ辺があれば、その辺を <math>(v,w)</math> と書く。

最短経路問題は、ビー玉と紐を用いて解くことができる。
まずビー玉を頂点、紐を辺にするグラフを工作する。
グラフを板の上に置き、スタートの頂点にあたるビー玉だけをつまむ。
グラフが置かれている板を取り除くと、グラフは自由落下を始めるが、
スタートにあたるビー玉を持っているので、スタート地点から近いビー玉から順に落下が止まる。
ゴールにあたるビー玉が止まったとき、ゴールにあたるビー玉はスタートにあたるビー玉まで紐で一直線で結ばれている。
この直線が最短経路である。

落下が止まった頂点 <math>v</math> に対し、<math>v</math> を支えている頂点 <math>w</math> が存在する。
<math>w</math> を <math>v</math> の「直前の頂点」と呼ぶことにする。
以下簡単のため、直前の頂点は1つしかないと仮定して話を進めるが、
一般の場合も同様である。

ダイクストラのアルゴリズムは、上述の解法をコンピュータ上でシミュレートしたものである。
グラフ <math>G=(V,E)</math>、スタートとなる頂点 <math>s</math>、および各辺 <math>e</math> の長さ <math>\text{length}(e)</math> が入力として与えられると、
このアルゴリズムは上述の解法をシミュレートし、「落下」が停止した頂点から順に、その頂点の直前の頂点が何であるかを出力する。
ゴールとなる頂点の「落下」が停止したところで、ダイクストラのアルゴリズムを止めれば、
あとはゴールから順に、直前の頂点、さらにその直前の頂点とたどっていくことで、
ゴールとスタートをつなぐ最短経路(の一つ)を求めることができる。

=== 詳細 ===
以上の考察から分かるように、ダイクストラ法では「次に落下が停止する頂点」（とその直前の頂点）を求めることが重要である。
そこでこれらを効率的に求める方法を説明する。

現時点で「落下」が停止している頂点の集合をHとし、
各頂点 <math>v \in V</math> に対して <math>H \cup {v}</math> 内での <math>v</math> と <math>s</math> との最短距離を <math>d(v)</math> とする（<math>H \cup {v}</math> 内で <math>s</math> から <math>v</math> に到達できないときは <math>d(v)=\inf</math> とする）。
さらに、<math>H</math> に隣接している頂点の集合を <math>A</math> とする。
ここで頂点 <math>v</math> が <math>H</math> に隣接しているとは、<math>v</math> と <math>H</math> 内のいずれか頂点を結ぶ辺が存在することを指す。

次に落下が停止する頂点を <math>u</math> とし、<math>u</math> の直前の頂点を <math>w_u \in H</math> とすると、
以下が成立することが分かる。

* <math>u</math> は <math>A</math> に属し、しかも <math>A</math> 内で <math>d(u)</math> が最小になる頂点である。
* <math>s</math> から <math>u</math> への最短経路は <math>w_u \in H</math> を通る。

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

* 集合 <math>H</math> と集合 <math>A</math>
* 各頂点 <math>v \in V</math> に対して <math>H \cup {v}</math> 内での <math>s</math> から <math>v</math> への最短距離 <math>d(v)</math>。
* 各 <math>v \in A</math> に対し、<math>v</math> の直前の頂点 <math>w_v</math>

ダイクストラ法では、<math>A</math> 内で <math>d(u)</math> が最小になる頂点 <math>u</math>（<math>=</math>次に落下が停止する頂点）を求めて <math>u</math> を出力し、それにあわせて管理しているデータを更新し、そしてさらに次に落下が停止する頂点を求める、という操作を繰り返す。

そこで最後に、ダイクストラ法が管理しているデータを更新する方法を述べる。

<math>A</math> 内で <math>d(u)</math> が最小になる頂点 <math>u</math>（<math>=</math>次に落下する頂点）が求まったら、まず <math>u</math> を <math>H</math> に追加する。それにあわせて <math>A</math> から <math>u</math> を除去し、<math>u</math> に隣接していてかつ <math>H</math> に属さない頂点を <math>A</math> に加える。

<math>u</math> を <math>H</math> に追加した結果「<math>H \cup {v}</math> 内での <math>s</math> から <math>v</math> への最短距離」である <math>d(v)</math> が変化するのは、
<math>u</math> と <math>v</math> とを結ぶ辺がある場合に限られる。

<math>u</math> を <math>H</math> に追加後の「<math>H \cup {v}</math> 内での <math>s</math> から <math>v</math> への最短距離」は次のいずれかと一致する。

* (a) <math>u</math> を <math>H</math> に追加する前の段階での <math>s</math> から <math>v</math> への最短経路
* (b) <math>u</math> を <math>H</math> に追加する前の段階での <math>s</math> から <math>u</math> への最短経路を通った後で <math>u</math> と <math>v</math> を結ぶ辺を通るという経路

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

以上の考察より、<math>d(v)</math> および <math>w_v</math> を次のように更新すればよいことがわかる：

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

== 注釈 ==
<references group="注釈"/>

== 引用 ==
{{reflist|2}}

== 参考文献 ==
* Dijkstra, E.W. (1959). [http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf ''A note on two problems in connexion with graphs'']. In ''Numerische Mathematik'', 1 (1959), S. 269 ～ 271.
* {{cite book
|和書
|last1      = コルテ
|first1     = B. 
|last2      = フィーゲン
|first2     = J. 
|year       = 2009
|title      = 組合せ最適化 : 理論とアルゴリズム
|edition    = 第2版
|url        = {{google books|7OfUJPqwyKwC|組合せ最適化 : 理論とアルゴリズム|page=184|plainurl=yes}}
|pages      = 184&ndash;185
|publisher  = シュプリンガー・ジャパン
|isbn       = 978-4431100218
|ref        = harv
}}

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

{{最適化アルゴリズム}}
{{アルゴリズム}}

{{DEFAULTSORT:たいくすとらほう}}
[[Category:エドガー・ダイクストラ]]
[[Category:アルゴリズム]]
[[Category:グラフ理論]]
[[Category:組合せ最適化]]
[[Category:数学に関する記事]]
[[Category:エポニム]]