为什么Dijkstra的时间复杂度是O((V + E) logV)

Question

我正在阅读有关使用二元堆的 Dijkstra 算法的最坏情况时间复杂度（该图表示为邻接列表）。

根据维基百科（https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Running_time）和各种stackoverflow问题，这是

O((V + E) logV)

，其中E - 边数，V - 顶点数。但是我没有找到任何解释为什么不能在

O(V + E logV)

中完成。

使用自平衡二叉搜索树或二叉堆，该算法在最坏情况下需要

Θ((E+V) logV)

时间

如果 E >= V，无论如何，复杂性都会降低到

O(E logV)

。否则，我们在与起始顶点相同的连通分量中拥有

O(E)

顶点（一旦到达它们，算法就会结束）。在每次迭代中，我们都会获得这些顶点之一，并花费

O(logV)

时间将其从堆中删除。 到连接顶点的距离的每次更新都需要

O(logV)

并且这些更新的数量受边 E 的数量限制，因此我们总共进行

O(E)

这样的更新。添加

O(V)

时间来初始化距离，我们得到最终的复杂度

O(V + E logV)

。

我哪里错了？

Answer 1

对于使用优先级队列实现的Dijkstra算法，我们以优先级队列操作作为成本模型。

1.) 用 V 个顶点初始化优先级队列需要 O(VlogV) 时间。

2.) 删除最小的（提取距源距离最小的顶点）需要 O(VlogV) 时间。

3.) 松弛边时更新每个顶点 * 假设所有边都松弛，则运行时间为 O(ElogV)。

因此，Dijkstra 算法的时间复杂度为 O((V+E)logV)，对于边数远大于顶点数的图，运行时间将为 O(ElogV)。