为何二叉堆实现的Dijkstra算法时间复杂度无法达到O(V+E logV)

嗨，我来帮你理清这个疑惑～你的推导里其实漏掉了一个关键的开销部分，导致结果不准确，具体拆解如下：

• 你忽略了「提取最小顶点」操作的总时间：
  Dijkstra算法中，每个顶点都会被从二叉堆中执行一次extract-min（提取当前距离最小的顶点）操作，总共要执行V次。而二叉堆的extract-min操作时间复杂度是O(logV)，所以这部分的总开销是O(V logV)——这部分不能和初始化的O(V)合并，毕竟V logV的增长速度远快于V，无法被后者覆盖。

• 再加上边的更新操作开销：
  每个边最多触发一次距离更新（decrease-key）操作，每次操作的时间同样是O(logV)，总共有E次这类操作，所以这部分开销是O(E logV)。

• 最后合并所有部分：
  把初始化的O(V)、提取顶点的O(V logV)、边更新的O(E logV)加起来，总复杂度是O(V + V logV + E logV)。由于V logV的增长速度比V快，所以最终可以简化为O((V + E) logV)。

补充两个常见的简化场景：

• 当图是稠密图（E ≥ V²）时，(V+E)logV ≈ E logV，复杂度可简化为O(E logV)；
• 当图是稀疏图（E ≈ V）时，(V+E)logV ≈ 2V logV，也就是O(V logV)，此时算法的主要开销来自提取顶点的操作。

内容的提问来源于stack exchange，提问作者martinkunev