ダイクストラ法の実行時間

質問

ダイクストラ法の実行時間が，
O(n)なのは様々なサイトを見ていると分かるのですが，
なぜ，O(n^2)なのかが分かりません．
それと，ヒープを使った際に，
O((n+m)log(n))になる理由がわかりません．

どなたか，分かりやすい解説をお願いします．

回答No.1

noocyte · ベストアンサー

ｎは節点の数，ｍは辺の数ですか？

Dijkstra のアルゴリズムの主要部分は，次の２つの繰り返し．

(1) 最短路が確定していない節点の集合Ｑの中から，
　　始点ｓに最も近い節点Ｐを１つ選んで取り出す．

(2) Ｐの隣接点の最短距離を更新．

Ｑの初期値は，全節点から始点ｓを除いたものなので，
全節点数をｎとするとその要素数はｎ－１．
したがって上記のループ回数はｎ－１回で，
Ｑの要素数ｑはｎ－１，ｎ－２，…，２，１と変化する．

(1) の最小要素を求める処理を単純な全数比較で行う場合，
　　ｑ－１回の比較が必要．これを全ループ回数分合計すると

　　　Σ{q=1,n-1} (q-1) ＝ (1/2) (n^2 - 3 * n + 2) 回の比較 → O(n^2)

(2) の処理時間は，Ｐの隣接点の個数，つまりＰから出る辺の数に比例する．
　　これを全ループ回数分合計すると，グラフのすべての辺について１回ずつ
　　処理することになるので，処理時間は辺の総数ｍに比例する．
　　つまり O(m)．辺の総数が最大になるのは完全グラフの場合で，
　　ｍ≦nC2＝ n * (n-1) / 2．したがって O(m)≦O(n^2)．

したがって Dijkstra のアルゴリズムの処理時間は (1) と (2) を合計して，
O(n^2 ＋ m) ≦ O(n^2 ＋ n^2) ＝ O(n^2)．

Ｑを始点からの距離で順序付けたヒープで管理する場合は，最小値を見つける
手間は O(1) だが，それを取り出す (削除する) のに O(log(n)) の手間がかかる．
これを約ｎ回繰り返すので合計 O(n * log(n))．

また (2) において，各節点の距離を更新する場合，ヒープから一旦削除
(O(log(n)) して再登録 (O(log(n)) する必要があるので１回あたり

O(log(n)) ＋ O(log(n)) ＝ O(log(n))．

これを辺の数だけ繰り返すので O(m * log(n))．

以上を合計すると，

O(n * log(n)) ＋ O(m * log(n)) ＝ O((m + n) * log(n))．

… 合ってるかな？

まあ，↓アルゴリズムのデモでも見ながら考えてください．(笑)

Algorithm Demo (最短路問題)
http://www-or.amp.i.kyoto-u.ac.jp/research/demo/SP.html

お礼

とても丁寧な返答，ありがとうございます．
参考意見となっていますが，ものすごく参考になります！
助かりました！
これで，なんとかなりそう・・・です．