Dijkstra 演算法的這個特定實作的時間復雜度是多少？
我知道當你使用最小堆時，這個問題的幾個答案是O(E log V)，這篇文章和這篇文章也是如此。但是，這里的文章說 O(V ElogE) 并且它與下面的代碼具有相似（但不完全相同）的邏輯。
演算法的不同實作可以改變時間復雜度。我正在嘗試分析下面實作的復雜性，但是諸如檢查visitedSet和忽略重復頂點之類的優化minHeap讓我懷疑自己。
這是偽代碼：
// this part is O(V)
for each vertex in graph {
distanceMap[vertex] = infinity
}
// initialize source vertex
minHeap.add(source vertex and 0 distance)
distanceMap[source] = 0
visitedSet.add(source vertex)
// loop through vertices: O(V)?
while (minHeap is not empty) {
// Removing from heap is O(log n) but is n the V or E?
vertex and distance = minHeap.removeMin
if (distance > saved distance in distanceMap) continue while loop
visitedSet.add(vertex)
// looping through edges: O(E) ?
for (each neighbor of vertex) {
if (visitedSet contains neighbor) continue for loop
totalDistance = distance weight to neighbor
if (totalDistance < saved distance in vertexMap) {
// Adding to heap is O(log n) but is n the V or E?
minHeap.add(neighbor and totalDistance)
distanceMap[neighbor] = totalDistance
}
}
}
筆記：
- 從源頂點可到達的每個頂點將至少被訪問一次。
- 檢查每個頂點的每條邊（鄰居），但如果在
visitedSet - 只有當鄰居的距離比當前已知的距離更短時，才會將鄰居添加到堆中。（假設未知距離的默認長度為無窮大。）
這個實作的實際時間復雜度是多少？為什么？
uj5u.com熱心網友回復：
盡管進行了測驗，但 Dijkstra 的這種實作可能會將 Ω(E) 項放入優先級佇列。對于每個基于比較的優先級佇列，這將花費 Ω(E log E)。
為什么不是 E log V？好吧，假設一個連接的、簡單的、非平凡的圖，我們有 Θ(E log V) = Θ(E log E) 因為 log (V?1) ≤ log E < log V2 = 2 log V。
Dijkstra 演算法的 O(E V log V) 時間實作依賴于 (n 攤銷) 恒定時間 DecreaseKey 操作，避免單個頂點的多個條目。然而，在稀疏圖的實踐中，這個問題的實作可能會更快。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/391644.html