Dijkstra 算法的时间复杂度

Question

我在很多文章中看到，这里也看到dijkstra的时间复杂度是

O(V + ElogV)

但时间复杂度不应该是

O(V + ElogE)

吗？

这是我的解释

Set all nodes distance to infinity and source distance to 0 -> O(V) time
Add source node to priority queue

//priority queue will have a maximum of |E| elements and popping or inserting from priority queue                                                                                          
//is done in O(Log|E|) time. So the total complexity for the while loop is O(ElogE)

while the priority queue is not empty:
    pop min from the priority queue -> O(logE) time
    if the popped element is visited:
         continue
    else mark the popped element as visited
    for all edges from popped node (u, v, w):
         if dist[v] > dist[u] + w:
              dist[v] = dist[u] + w
              add (v, w) to the priority queue -> O(logE)

那么时间复杂度不应该是

O(V) + O(ElogE) = O(V + ElogE)

吗？

Answer 1

您的错误是假设

ExtractMin()

（或您所说的

pop min

）的运行时间是

O(log E)

- 但这个运行在

O(log V)

。

• ExtractMin 运行时

  O(log V)

  被调用

  |V|

  次。
• 为了创建最小堆，您需要时间

  O(V)

  。
• 每次减少操作需要

  O(log V)

  时间，并且有

  =<|E|

  个这样的操作。

所以运行时复杂度是

O((V+E) log V)

，即

O(E log V)

（加上初始化所需的时间，所以总体来说是

O(V + E log V)

）。

更详细的分析可以在 CLRS 第 24.3 章中找到。

Answer 2

我相信这取决于你的实施。查看您的伪代码，看起来您执行 heappush() 导致具有不同距离值的重复节点，而不是执行减少操作的实现，即它们更新堆内节点的距离，因此 log(V) 实际上变成 log(E) .

Answer 3

你是对的，如果将节点的新 dist 值推送到堆而不是减少该节点的值，则堆最多将有 E 个节点。实际上，由于 E 在完整图中最多与 V^2 成比例，因此 extractMin 操作的时间复杂度将为 O(logV)，来自 O(log(E)) = O(log(V^2) = O(2*logV ) = O(log(V)。因此，对于连通图或几乎连通图，总体时间复杂度为 O(ElogV)，因为我们将为每条边执行 extractMin，我们可以忽略具有 O(V) 时间复杂度的初始化部分，因为在这种情况下，E 与 V^2 成比例。对于稀疏图，我们应该将该部分添加到复杂度中，并且其余的时间复杂度不会改变，因为 E 小于 V^2，因此此实现会产生额外的空间复杂度。如果您要更改优先级，如果我们忽略存储图的复杂性，空间复杂度将为 O(V)，但在此实现中，您将具有 O(E) 空间复杂度。