可处理负权边的改进版Dijkstra算法的时间复杂度

标准Dijkstra算法的局限性 #

标准Dijkstra算法的核心假设是：一旦某个节点被从优先队列中取出并标记为“已处理”，就认为找到了到该节点的最短路径，后续不会再更新它。但当图中存在负权边时，这个假设会被打破——已经被标记为“已处理”的节点，可能会通过一条包含负权边的路径得到更短的距离，此时标准算法无法捕捉到这种更新，导致结果错误。

改进版的核心调整 #

能处理负权边的改进版Dijkstra算法，主要做了以下两点关键修改：

• 移除“节点处理完成后标记为不可更新”的逻辑：允许同一个节点多次被加入优先队列，只要能找到更短的路径，就可以重新进入候选处理池。
• 增加路径有效性检查：每次从优先队列中取出节点时，先对比当前记录的该节点最短路径与取出的路径长度。如果取出的路径比已记录的最短路径更长，直接跳过该节点的后续处理，避免无效操作。

需要注意的是：这种改进版仍然无法处理包含负权环的图——负权环会让路径长度无限减小，不存在最短路径，算法会陷入无限循环。

时间复杂度 #

最坏情况下，图中的每条边都可能触发一次节点入队操作，而优先队列的插入/取出操作时间复杂度为O(logV)（V是节点数），因此整体时间复杂度为O(E logV)（E是边数）。

在实际场景中，如果负权边数量不多，这种改进版的运行效率通常优于Bellman-Ford算法（O(VE)），但在负权边密集的图中，表现可能不如基于队列实现的SPFA算法。

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