具有最小堆和优化的 Dijkstra 算法的时间复杂度

Question

Dijkstra 算法的这个特定实现的时间复杂度是多少？

我知道 this question say O(E log V) when you use a min heap, and so does this article and this article. However, the article here 的几个答案说 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
只有当邻居的距离小于当前已知距离时，才会将邻居添加到堆中。（假定未知距离的默认长度为无穷大。）

这个实现的实际时间复杂度是多少？为什么？

Answer 1

尽管经过测试，Dijkstra 的这个实现可能会将 Ω(E) 个项目放入优先级队列中。对于每个基于比较的优先级队列，这将花费 Ω(E log E)。
为什么不是E log V？好吧，假设一个连通的、简单的、非平凡的图，我们有 Θ(E log V) = Θ(E log E) 因为 log (V−1) ≤ log E < log V² = 2 log V.
Dijkstra 算法的 O(E + V log V) 时间实现依赖于（n 摊销的）恒定时间 DecreaseKey 操作，避免了单个顶点的多个条目。然而，这个问题的实施在稀疏图上的实践中可能会更快。

具有最小堆和优化的 Dijkstra 算法的时间复杂度

Time complexity for Dijkstra's algorithm with min heap and optimizations

algorithm

big-o

graph

dijkstra

time-complexity