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)中。

具有运行时O(log V)的ExtractMin被调用|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(。