Dijkstra algorithm - hamadakoichi blog

"全てのEdge(辺)のWeight(重み)が非負の場合"に、
重みつき有向グラフ G=(V,E) に対する
Single-Source Shortest-Path Problem (単一始点最短路問題)、を解くことができる。

実装の仕方により、Dijkstra algorithmの実行時間は Bellman-Ford algorithmより短くすることができる。

Dijkstra algorithmは、始点 s からの最終的な最短路重みが既に決まっているVertex(頂点)の集合 S を管理する。最小の最短路推定値 d[u] を持つ頂点 u ∈ V-S を選び、u を S に追加し、u から出る辺に対して、緩和操作 Relax の実施を繰り返す。

V-Sの全てのvertexを含み、最短路推定値 dの値をキーとする優先度つき Queue Qを管理する。

Dijkstra(G,w,s)
1.　Initialize-Single-Source(G,s)
2.　S ← φ
3.　Q ← V[G]
4.　while Q ≠φ
5.　　do u ← Extract-Min(Q)
6.　　　S ← S ∪ {u}
7.　　　for each vertex v ∈ Adj[u]
8.　　　　do Relax(u,v,w)

Initialize-Single-Source(G,s), Relax(u,v,w)はRelaxation(緩和操作)を参照

[実行時間(計算量)]

Dijkstra algorithmの実行時間は、"Min-Priority Queue(優先度つきmin-Queue)"の
実装方法に依存している。

　(1) Initialize-Single-Source(G,s)は O(V),
　[Min-Priority Queue操作]
　(2) Insert(3行目)は、　　　　　　|V|回 × Insert実行時間
　(3) Extract-Min (5行目)は、　　　|V|回 × Extract-Min実行時間
　(4) Decrease-Key(8行目 Relax)は、|E|回 × Decrease-Key実行時間
　　 (For Loopの繰り返し数 |E|回)

・[Min-Priority Queueの実装例１：1から|V|に番号が振られた頂点を使用]
　単に配列のv番目の位置に最短路推定値 d[v] を記憶すればよい。

　[2] Insertの実行時間　　 ... O(1)
　[3] Extract-Minの実行時間 ... O(V)
　[4] Decrease-Keyの実行時間 ...O(1)

　⇒全体の実行時間 O(V^2 + E) = O(V^2)

・[Min-Priority Queueの実装例２：min-heapの使用]
　グラフが十分に疎 (E =o(V^2 /logV))である場合の実用的な方法。

　(2) Min-Heapの実現... O(V)
　[3] Extract-Minの実行時間 ... O(logV)
　[4] Decrease-Keyの実行時間 ...O(logV)

　⇒全体の実行時間 O((V+E)logV)。
　　全ての頂点が、始点 s から到達可能な場合、O(E logV)
　　（E=o(V^2/logV)の場合における O(V^2)時間の改良）

・[Min-Priority Queueの実装例３：Fibonacci Heap(フィボナッチヒープ)の使用]

　[3] Extra-Minのならし実行時間 ... O(logV)
　[4] Decrease-Keyのならし実行時間...O(1)

　⇒全体の実行時間 O(VlogV +E)

[Reference]:
Introduction to Algorithms, Second Edition
アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)