Dijkstras Algorithm两种实现对比：带visited数组版本为何测试失败

Code1执行失败的核心原因 #

这两种实现本质是完全不同的最短路径算法逻辑，通过率差异的核心问题有两个：

1. vis数组的使用逻辑错误，且入队规则不符合Dijkstra算法要求
   标准Dijkstra算法的vis数组作用是标记已经确定最短路径的节点：算法默认图中所有边权重非负，所以优先队列弹出的节点的最短距离已经是全局最小值，后续不需要再处理。你的Code1有两个明显的逻辑漏洞：

• 弹出节点后没有先判断vis[u] == 1就直接标记处理，会重复处理队列中遗留的同一节点的旧的、更长距离的无效条目
• 不管邻接节点的最短距离有没有被更新，只要vis[v] == 0就盲目将节点加入优先队列，会生成大量无效条目，极端情况下会打乱节点处理顺序

2. 两种实现的适用场景完全不同
   你写的Code2本质是SPFA（最短路径快速算法），它移除了vis数组的限制，允许同一个节点多次入队，只要能更新出更短的路径就继续处理，天生支持带负权边的图（只要不存在负权环）。而带vis数组的Dijkstra算法只能处理无负权边的图，如果你的测试用例中存在负权边，Code1的核心假设直接失效，必然会算出错误结果。

触发错误的典型边界场景 #

只要满足以下任意一种情况，Code1就会执行出错：

• 测试用例存在负权边：举个最简单的可复现用例
  节点：S（起点）、A、B、C
  边权重：S→A=1，A→C=1，S→B=2，B→A=-2
  正确的S到C的最短路径为S→B→A→C，总权重为2-2+1=1
  走Code1逻辑时，优先队列会先弹出距离为1的A，标记vis[A]=1并更新C的距离为2；后续弹出B处理邻接A时，因为A已经被标记为已访问，直接跳过更新，最终得到的C的距离为2，和正确结果不符。而Code2因为没有vis数组的限制，会正常更新A的距离为0，后续重新处理A时更新C的距离为1，得到正确结果。
• 图中存在多条路径可达同一节点，且短路径的邻接处理晚于长路径的节点弹出：即使没有负权边，如果你入队时误将边权重当做节点总距离放入优先队列，导致优先队列排序错误，也会出现vis提前标记节点，错过更短路径更新的问题。

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