Dijkstra最小堆算法的时间复杂度及其优化

Question

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

我知道这个问题的几个答案是，当你使用最小堆时，O（E log V），这篇文章和这篇文章也是如此。然而，这里的文章说的是O（V ElogE），它的逻辑与下面的代码类似（但不完全相同）。

算法的不同实现可以改变时间复杂度，我试图分析下面实现的复杂性，但是像检查visitedSet和忽略minHeap中的重复顶点这样的优化让我怀疑自己。

以下是伪代码：

dart prettyprint-override">// 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

>

为什么不呢？假设一个连通的，简单的，非平凡的图，我们有Θ（E log V）=Θ（E log E）自log（V）−1) ≤ 日志E

算法依赖于单个顶点的时间常数。然而，在稀疏图上实现这个问题可能会更快。