优先队列实现Dijkstra算法时间复杂度是否超过O(VlogV)？

问题结论 #

你实现的这种基于二叉堆优先队列、允许同一顶点多次入队的Dijkstra算法，时间复杂度不会超过O(E log V)，不会出现量级更高的复杂度。

具体说明 #

• 你观察到外层循环次数大于顶点数V是完全正常的现象：优先队列中会存储同一顶点对应的多个旧的、权重更大的冗余条目，这些旧条目在弹出时，对应顶点已经被加入最短路径树（也就是你代码里的spt数组标记为true），不会产生额外的有效松弛操作。
• 复杂度推导：每次成功的松弛操作才会往优先队列里新增条目，一张图最多有E次有效松弛，因此优先队列的总操作次数是O(E)，每次二叉堆的入队、出队操作时间复杂度是O(log E)，而因为E ≤ V²，log E等价于O(log V)，因此整体时间复杂度为O(E log V)。
• 什么时候能达到O(V log V)？只有使用支持O(1)减小键操作的斐波那契堆作为优先队列，避免同一顶点重复入队的情况，才能达到O(V log V)的时间复杂度，普通二叉堆实现的版本普遍都是O(E log V)，这个复杂度对于稀疏图来说已经远优于朴素实现的O(V²)，符合你的优化预期。
• 额外优化提示：你当前的代码存在一处可优化的逻辑：初始化时就将spt[source]设为true是不必要的，且弹出元素后直接标记spt的逻辑没有判断该顶点是否已经被处理过，虽然不会影响最终结果，但会增加无效的邻接边遍历次数，建议修改为弹出元素后先判断spt[poppedElement.vertex]是否为true，如果为true直接跳过本轮循环即可。

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