Dijkstra 最短路径算法的贪心选择正确性及负权边失效原因

理解：Dijkstra 算法用于在一张图中，从一个起点出发，找出到其他所有节点的最短路径。它运行的前提是图中没有负权边（所有边的权重非负）。它之所以高效，靠的是每次选择当前距离起点最近的未处理节点，然后更新它的邻居。下面分两步解释：为什么这个“贪心”选择是正确的？为什么一出现负权边，它就会失效？

1. 贪心选择为什么正确

核心逻辑：因为所有边权非负，所以当算法选取当前距离最小的节点时，这个距离就是起点到该节点的最终最短距离，后面不可能再有更短的路径。

具体步骤

1. 初始化：将起点 s 的距离设为 0，其余所有节点距离设为 无穷大。标记起点为“已处理”，其余节点为“未处理”。

2. 重复以下操作，直到所有节点都被处理：

   • 从所有未处理的节点中，选出距离值最小的那个节点 u。
   • 将 u 标记为已处理（表示它的最短距离已经确定）。
   • 对 u 的每一个邻居 v，执行“松弛”：如果 dist[u] + w(u,v) < dist[v]，则更新 dist[v] 为这个更小的值。

3. 证明为什么第 2 步中的 u 不可能被更新：

   • 假设有一个未处理的节点 u，其当前距离是 d，算法认为它最小。那么所有其他未处理节点的距离都 ≥ d。
   • 如果有一条经过某个“已处理”节点 p 再到 u 的路径，由于 p 已处理，dist[p] 已确定且必然 ≤ d（因为 p 的处理顺序比 u 早），但这条路径经过 p 再走一条非负边到 u，总距离 = dist[p] + (非负) ≥ dist[p]，而 dist[p] ≤ d，所以不会比 d 小。
   • 如果有一条经过另一个“未处理”节点 q 再到 u 的路径，由于 q 未处理且 dist[q] ≥ d，加上一条非负边，总距离 ≥ d，同样不会更短。
   • 结论：d 就是最终最短距离，贪心选择正确。

一句话总结：非负权边保证了任何经过其它节点的路径，其长度都不会小于当前最小距离节点的当前距离。

2. 负权边为什么导致算法失效

问题：当图中存在负权边后，上述证明的第一步就崩塌了——一个节点即使被选为“当前最小”，也可能在后续被一条经过负权边的路径更新得更小，而算法已经将它标记为“已处理”，不会再检查它，最终导致错误结果。

示例图（文字描述）

• 节点 A（起点），节点 B，节点 C。
• 边：A→B 权重 5，A→C 权重 2，C→B 权重 -4。

执行步骤与错误

1. 初始化：dist[A]=0，dist[B]=∞，dist[C]=∞。

2. 第一次循环：从未处理节点中选取距离最小的节点，即 A（距离 0）。标记 A 为已处理。松弛 A 的邻居：更新 dist[B]=5，dist[C]=2。

3. 第二次循环：未处理节点中有 B（5）和 C（2），选取距离最小的 C（2）。标记 C 为已处理。松弛 C 的邻居：检查 C→B（权重 -4），发现 dist[C] + (-4) = 2 - 4 = -2 小于当前 dist[B]=5，于是将 dist[B] 更新 为 -2。但此时 B 仍然是“未处理”节点，而 C 已被标记为“已处理”——问题就在这里：C 是已知的最小节点，但后来它通过负权边更新了 B，而 B 比 C 更小（-2 < 2），实际上 C 已经不可能是从 A 到 C 的最短路径了。因为这条新路径 A→C→B 中，C 只是中间点，最终到达的是 B，但算法没有重新检查 C 是否还能通过 B 再被更新（比如 A→C→B→... 回 C）。

4. 第三次循环：现在未处理节点只有 B（距离 -2），选取 B，标记为已处理。松弛 B 的邻居（假设没有）。算法结束。结果：dist[C] 依然是 2，但实际最短路径 A→C→B→? 不涉及回 C，但更重要的是，A 到 C 的最短路径只经过直接边 2，所以 dist[C]=2 是对的。但如果图再多一个负权回路，算法会彻底混乱。即使没有回路，贪心选择也错误地认为 C 一旦被处理就不会再被更新，但实际上 C 通过 B 可能获得更短路径（比如增加一条负权边从 B 回到 C）。这个例子中，C 没有被更新，但主要错误在于：算法在 C 被标记为已处理后，仍然通过 C 更新了 B，而 B 比 C 更小，这违反了“最小距离节点一定是最短”的断言。

更典型的反例：假如有一个三角形 A→B（1），B→C（-2），A→C（10）。起点 A，初始化后选 A，更新 B=1, C=10。然后选最小未处理 B，标记 B 已处理，松弛 B→C 得 1-2=-1，更新 C=-1。但此时 C 距离 -1 小于 B 的 1，而 B 已被标记为不再更新。实际最短路径 A→B→C 是 -1，算法正确。但如果再加一条边 C→A（-1），形成负环，算法会在无限循环中崩溃。总之，负权边破坏了“当前最小距离节点不可能被后续路径更新”的前提。

3. 关键结论

• 正确条件：所有边权 ≥ 0 时，Dijkstra 的贪心选择是正确的。
• 失效原因：负权边允许在“已处理”的节点之后，通过一条负权边产生更短的距离，使之前被选中的节点不再是全局最小，而算法不会再回头更新它。补救措施：若图中有负权边，应改用 Bellman-Ford 算法或 SPFA。