O(N^2)の Dijkstra's algorithm
グラフ理論の一つである、Dijkstraのアルゴリズムは単一の出発点からのshortest path(最短経路)を求める方法としてとても有名です。道案内の経路探索などで使われることが多いとのこと。探してみると、Java言語による実装やAppletを使って視覚的に見せてくれているところなどがいくつもありました。例えば、
- http://renaud.waldura.com/doc/java/dijkstra/
- http://oopweb.com/Algorithms/Documents/AnimatedAlgorithms/VolumeFrames.html
- Shortest Path Problem: Dijkstra's Algorithm
など。
アルゴリズムそのものは、それほど難しい訳ではないのですが、なかなかすんなりとのみこめないので、自分なりに理解したところをまとめておきます。
アルゴリズムの概略は
が簡潔にまとまっていました。また、
はiterationが進んでいくにつれて、どのような計算をしてどのように進めていくかがわかりやすく書いてあるのでとても参考になりました。
このiterationの過程を、http://renaud.waldura.com/doc/java/dijkstra/で取り上げられているa, b, c, dの4つのノードからなるdirected(有効)グラフに適用して、最短経路が求められるまでを書き出してみると、こんな感じになるはずです。
S: 訪問済みノードの集合 Q: 非訪問済みノードの集合 w: 現在のノード D[v]: 始点から非訪問済みノードまでの最小コストの配列 l(vi, vj): ノードvi, vj間のコスト Initially Mark a visited, S = {a}, Q = {b, c, d} and w = a D[w] = 0 D[b] = 4 D[c] = 2 D[d] = +∞ (no direct route from a to d) the first iteration Mark c visited, S = {a, c}, Q = {b, d} and w = c D[w] = 2 D[b] = MIN(D[b], D[w] + l(c, b)) = MIN(4, 2 + 1) = 3 D[d] = MIN(D[d], D[w] + l(c, d)) = MIN(+∞, 2 + 5) = 7 the second iteration Mark b visited, S = {a, c, b}, Q = {d} and w = b D[w] = 3 D[d] = MIN(D[d], D[w] + l(b, d)) = MIN(7, 3 + 1) = 4 the third iteration Mark d visited, S = {a, c, b, d}, Q = {} and w = d D[w] = 4 iteration S Q w D[w] D[b] D[c] D[d]0 {a} {b, c, d} a 0 4 2 +∞ 1 {a, c} {b, d} c 2 3 (2) 7 2 {a, c, b} {d} b 3 (3) (2) 4 3 {a, c, b, d} {} d 4 (3) (2) (4)
- -
このようにして、最短経路が求められるのですが、全てのノードに対してDを算出するところでO(N)のcomplexityになり、さらに、最小のDを求めるところでもO(N)必要なので、全体として二重ループをまわすことになり、O(N^2) (big-O of N squared)のcomplexityになるというものです。
しかし、このアルゴリズムには改善の余地があります。
- Dijkstra's algorithm for shortest paths « Python recipes « ActiveState Code(のコメント)
- Speeding up Dijkstra’s Algorithm 1 | Computer programming
などで、議論されていました。
そして、最初にあげたJavaによる実装でも、最小のDを求めるところでhttp://d.hatena.ne.jp/yokolet/20080629#1214800194のHeapSortでも使ったPriority Queueを利用してcomplexityを小さくする方法が使われていました。つまり、一つ目のO(N)はそのままですが、二つ目はO(log(M))になり、全体としてO(N*log(M))になります。ノード数が大きいときにはスピードアップを期待できるはずです。
