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

Question

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
• 仅当邻居的距离比当前已知距离短时，才会将其添加到堆中。（假定未知距离的默认长度为无穷大。）

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

Answer 1

\n

1. 尽管经过测试，Dijkstra 的这种实现可能会将 \xce\xa9(E) 项放入优先级队列中。对于每个基于比较的优先级队列，这将花费 \xce\xa9(E log E) 。

   \n
\n

2. 为什么不是 E log V？好吧，假设一个连通的、简单的、非平凡的图，我们有 \xce\x98(E log V) = \xce\x98(E log E) 因为 log (V\xe2\x88\x921) \xe2\x89\xa4 log E < log V\xc2\xb2 = 2 log V。

   \n
\n

3. Dijkstra 算法的 O(E + V log V) 时间实现依赖于 (n 摊销) 常数时间 DecreaseKey 操作，避免单个顶点的多个条目。然而，在稀疏图的实践中，这个问题的实现可能会更快。

   \n
\n

\n