修改Dijkstra算法适配负权重及时间复杂度探讨
一、修改后的时间复杂度绝非仅差常数
标准Dijkstra算法的高效核心在于：每个节点只会被从优先队列中弹出一次，标记为已处理后就不再触碰。用二叉堆实现时时间复杂度为O(M log N)，斐波那契堆实现更是能达到O(M + N log N)的最优线性对数级。
但你提到的修改方案打破了这个核心逻辑：一旦发现已处理节点有更短路径，就将其从已处理集合移除并重新入堆。这种情况下，同一个节点可能被多次加入堆中——在负权边存在的场景下，节点入堆的次数可能和边数正相关，极端场景下每个节点的入堆次数会达到O(M)级别。
如果用二叉堆实现，虽然理论上时间复杂度量级还是O(M log N)（堆操作次数等于边数级别），但斐波那契堆的最优复杂度优势会彻底丧失——因为重新入堆是全新的插入操作，而非原算法中高效的decrease-key操作，时间复杂度会退化为O(M log N)。更关键的是，实际运行中的常数开销会大幅上升：堆里会堆积大量冗余的节点条目，每次弹出都要额外判断当前记录的最短路径是否比堆中条目更优，这会带来很多无意义的计算。
二、即便时间复杂度量级不变，仍不适合负权图的原因
实际性能打折扣，失去原算法优势
标准Dijkstra的性能优势完全建立在“节点仅处理一次”的特性上，修改后这个特性消失，虽然理论复杂度量级没变，但实际运行效率会比标准版本低很多，甚至在负权边密集的场景下，不如专门针对负权图设计的Bellman-Ford或SPFA算法。代码复杂度提升，维护成本更高
为了实现“移除已处理节点并重新入堆”，需要额外维护哈希集合与哈希表的同步逻辑，代码比标准Dijkstra复杂不少，还容易出现边界错误（比如集合与堆的状态不一致）。概念定义的边界问题
通常我们说“Dijkstra算法不适用于负权图”，指的是标准版本的算法。你修改后的版本本质上是混合了Dijkstra的堆优化和Bellman-Ford的重复松弛逻辑，已经不属于纯粹的Dijkstra算法范畴了。
内容的提问来源于stack exchange，提问作者Slaycapь
