ダイクストラ法 - 情報科学と人工知能のノート

グラフ上の最短経路問題を解くアルゴリズム．エドガー・ダイクストラが 1959 年出版の論文で提案．

入出力

入力：グラフ $G=(V,E)$ 、コスト関数 $c:E\rightarrow\mathbb{Q}_{\geq 0}$ 、始点 $s\in{V}$ 、終点 $t\in{V}$ ．
解：始点から終点への経路．すなわち、次を満たす頂点の列（ただし）．
- $v_0=s$ 、
- $v_k=t$ 、
- 任意の $i\in[1,\cdots,k]$ について $\{v_{i-1},v_{i}\}\in E$ ．
解のコスト：経路に含まれる各辺のコストの和．
出力：コスト最小の解．

直観的なアイディア

まず前提として、始点ではない任意の頂点 $v$ について、始点から $v$ への最短経路は、始点から別の頂点 $u$ への最短経路に $v$ を加えた形に必ずなっています．何故ならば、始点から $u$ への最短ではない経路に $v$ を付け加えた形の経路は、 $u$ への経路の部分を最短経路に置き換えることによってコストを削減することができるからです．

よって、終点に単一の辺で接続されている頂点への最短経路に終点を加えたもののうち、コストの最も小さなものを選べばそれが始点から終点への最短経路になっているわけですが、すると今度は始点から別の頂点への最短経路問題を解かなければなりません．
ダイクストラ法ではこれを以下のような考え方によって効率よく求めていきます．

まず、始点と単一の辺で繋がっている頂点のうち、始点との間の辺のコストが最も小さい頂点を探します．これを $v$ とおきます．ちゃんと書くと

$v=\arg\min_{u\in{V}:\{s,u\}\in{E}}c(\{s,u\})$

です．このとき、始点から $v$ への最短経路は、 $(s,v)$ です．何故ならば、始点から直接 $v$ に向かわずに迂回してより小さいコストの経路を探そうと思うと、始点から次の頂点へ移動した段階で辺 $\{s,v\}$ のコストを超えてしまうからです．また辺のコストは非負であるため、経路のコストは経路の後ろに頂点を付け足していく分には単調非減少なので、 $(s,v)$ より小さなコストの経路を作ることはできません．

次は、 $(s,u')$ という形と、 $(s,v,u'')$ という二つの形の経路の中で、コストが最も小さいものの終端頂点を $v'$ とおきます（ただし $u'$ として $v$ は除く）．ちゃんと書くと

$u'=\arg\min_{u\in{V}\setminus\{v\}:\{s,u\}\in{E}}c(\{s,u\})$
$u''=\arg\min_{u\in{V}\setminus\{s,v\}:\{v,u\}\in{E}}c(\{s,v\})+c(\{v,u\})$

とおいて、 $c(\{s,u'\})$ の方が $c(\{s,v\})+c(\{v,u''\})$ よりも小さければ $v'=u'$ で、逆なら $v'=u''$ です．
すると、やはり同様に、仮に $v'=u'$ ならば $(s,v')$ よりも小さなコストの経路で $v'$ に至ることはできませんし、また $v'=u''$ ならば $(s,v,v')$ よりも小さなコストの経路で $v'$ に至ることはできません． $s$ または $v$ から迂回してより小さなコストの経路を探そうと思うと、最初の一歩で今注目している経路のコストを超えてしまうからです．

擬似コード

以上を繰り返して、始点に近い頂点から順にその頂点への最短経路を定めていくアルゴリズムがダイクストラ法です．
ただし、ダイクストラ法では各頂点への最短経路のコストのみを計算していって、終点への最短経路のコストが決定された後に、一気に最短経路を求めます．
以下に擬似コードを示します（簡単のため $c(\{u,v\}) = \infty, \forall \{u,v\}\in V^2\setminus E$ としました）．

$C[v]\leftarrow\infty,\forall{v\in{V}}$ ; // 始点から各頂点への最短経路のコストを格納する配列
$D[v]\leftarrow 0,\forall{v\in{V}}$ ; // 各頂点への最短経路のコストが定まっているかどうかを示す
$C[s]\leftarrow 0$ ;
${\rm while}\ D[t]=0$ ;
　　 $v=\arg\min_{u\in{V}:D[u]=0}C[u]$ ;
　　もし $v$ を取れなければ「解なし」を出力して終了;
　　 $D[v]\leftarrow{1}$ ;
　　 ${\rm for}\ u\in{V}$
　　　　 ${\rm if}\ C[v]+c(\{v,u\}) < C[u]\ {\rm then}$
　　　　　　 $C[u]\leftarrow C[v]+c(\{v,u\})$ ;
${\rm endwhile}$
// この時点で始点から終点への最短経路のコストが定まっている．
$v\leftarrow t$ ;
${\rm while}\ v \neq s$
　　 $C[v] = C[u] + c(\{v,u\})$ と $D[u]=1$ を満たす $u$ を任意に一つ選ぶ;
　　 ${\rm output}\ v$ ;
　　 $D[v] \leftarrow 0$ ; // コスト関数が非負ではなく正なら必要はない
　　 $v \leftarrow u$ ;
${\rm endwhile}$
${\rm output}\ s$ ;

計算量

計算モデルにチューリングマシン等を使うなど堅苦しいことは言わずに、上記の擬似コード上での使用メモリと動作ステップ数を数えます．入力されたグラフの頂点数を $n$ とおきます．

まず、使用した配列は $C$ と $D$ の二つだけなので必要な作業メモリは $O(n)$ ワードです．

最初の while ループは最大でも $n$ 回しか回りません．一回ごとに $D$ が $0$ な頂点が一つ選ばれ、その頂点の $D$ の値が $1$ になり、一度 $D$ の値が $1$ になった頂点の値は $0$ に戻らないため、高々頂点の個数回しかループが回らないからです．
同様に、二つ目の while ループも最大 $n$ 回しか回りません．

また、最初の while ループの中身を見ると、 $\min$ のところと ${\rm for}$ のところで for 文が $n$ 回ずつ回っています．
二つ目の while ループの中でも $u$ を得るために $n$ 回 for 文が回ります．

以上をまとめると、上記の擬似コードのステップ数は $O(n^2)$ となります．

ヒープを使ったときの時間計算量

辺の本数を $m$ とおくと、ダイクストラ法の時間計算量は $O(m\log n)$ だとか $O(n \log n + m)$ だとか、文献によって異なる記述が見つかるかもしれません．これは頂点の隣接関係が隣接リストで与えられているときに、最初の while ループの $v$ の探索のためにヒープを使って頂点を管理する場合の時間計算量です．

やり方は詳しく述べませんが、最小ヒープというものを使うと時間計算量は $O(m\log n)$ になります．また、フィボナッチヒープというものを使うとならしの時間計算量が $O(n \log n + m)$ になります．Brodal queue というものを使うと最悪時時間計算量が $O(n \log n + m)$ になるらしいです*1．
同じ頂点同士を結ぶ辺を高々一つしか持たない単純有向グラフの場合、 $m$ は最高で $m = n(n-1)$ となるので最小ヒープが最悪ですね．

ただし、これらはあくまでも理論的な時間計算量です．ヒープを使わないもの、最小ヒープを使うもの、フィボナッチヒープを使うものの三種類を実装して実行時間を比較してみたところ、時間計算量的には一番性能の悪い最小ヒープを使うものが一番速かったです*2．フィボナッチヒープは最小ヒープよりも若干遅く、グラフがメモリに載りきるようなサイズの問題でわざわざ実装するほどのものではありませんでした*3．これは理論的に時間計算量の良いアルゴリズムは、大抵オーダで隠れている定数部分に大きな定数を隠しているためです．

*1:読もうと試みたけどよくわかりませんでした．

*2:書いたのは結構昔なのでソースはどこかにいきました．グラフは平面グラフだったような気もする．

*3:書くの大変でしたし．