为什么Dijkstra算法不能处理负权边：贪心选择的失效

理解 Dijkstra 算法的核心：它是一个贪心算法，用于在带权有向图中找到从单个源点到所有其他顶点的最短路径。它的核心思想是：总是选择当前已知距离源点最近且未被处理的顶点，并利用它去“松弛”邻接的边。

1. 识别 Dijkstra 算法的贪心策略

1. 初始化：将源点的距离设为 0，其他所有顶点的距离设为 ∞（表示无穷大）。所有顶点都标记为未访问。
2. 选择：从所有未访问的顶点中，选择距离源点最近的顶点 u。
3. 标记：标记顶点 u 为已访问。这意味着 u 的最终最短路径已经确定，不会再改变。
4. 松弛：对于 u 的每一个未访问的邻居 v，检查通过 u 到达 v 的路径是否更短。计算公式为：
   $$d'(v) = d(u) + w(u, v)$$
   其中 d(v) 是当前记录的 v 到源点的距离，w(u, v) 是边 u -> v 的权重。如果计算出的新距离 d'(v) 小于 d(v)，则更新 d(v) = d'(v)。
5. 重复：重复步骤 2 到 4，直到所有顶点都被标记为已访问。

2. 理解“贪心选择”为何有效（在无负权边时）

• 核心前提：所有边的权重 w(u, v) 都必须 >= 0。
• 逻辑推理：当我们从“未访问”集合中选择距离最小的顶点 u 时，我们断言：已经找到了从源点到 u 的最短路径。
• 为什么可以这样断言？ 因为任何其他未被探索的路径，要想到达 u，都必须先经过某个“未访问”的顶点。由于边权为正，经过那个顶点的路径总长度必然大于该顶点自身的当前距离，而该顶点的当前距离又大于或等于 u 的当前距离。因此，不可能存在一条更短的路径到 u。
• 结论：在无负权边的情况下，贪心选择（总是选当前最近的）是安全且正确的。当前的“最近”就是全局的“最近”。

3. 复现一个包含负权边的错误场景

创建一个简单的图来演示：

• 顶点：A, B, C, D。
• 边与权重：
  • A -> B: 权重 2
  • A -> C: 权重 3
  • B -> C: 权重 -1 （负权边）
  • C -> D: 权重 2
  • B -> D: 权重 4
• 目标：从 A 到 D 的最短路径。

手动执行 Dijkstra 算法：

1. 初始化：d(A)=0, d(B)=∞, d(C)=∞, d(D)=∞。
2. 选择：选择 A（距离 0，最小）。标记 A 为已访问。
3. 松弛 A 的邻居：
   • 检查 B：d'(B) = d(A) + w(A, B) = 0 + 2 = 2。2 < ∞，更新 d(B)=2。
   • 检查 C：d'(C) = d(A) + w(A, C) = 0 + 3 = 3。3 < ∞，更新 d(C)=3。
4. 选择：从未访问的 {B, C, D} 中选择距离最小的顶点 B（距离 2）。标记 B 为已访问。
5. 松弛 B 的邻居（C 和 D）：
   • 检查 C：d'(C) = d(B) + w(B, C) = 2 + (-1) = 1。1 < 3，更新 d(C)=1。
   • 检查 D：d'(D) = d(B) + w(B, D) = 2 + 4 = 6。6 < ∞，更新 d(D)=6。
6. 选择：从未访问的 {C, D} 中选择距离最小的顶点 C（距离 1）。标记 C 为已访问。
7. 松弛 C 的邻居（D）：
   • 检查 D：d'(D) = d(C) + w(C, D) = 1 + 2 = 3。3 < 6，更新 d(D)=3。
8. 选择：选择最后一个未访问顶点 D（距离 3）。标记 D 为已访问。

算法结束，得到 d(D)=3，对应路径 A -> B -> C -> D，总权重 2 + (-1) + 2 = 3。在这个例子中，Dijkstra 似乎得到了正确答案。但这只是侥幸，因为负权边 B -> C 的作用在 B 被处理时就被利用了。

4. 指出根本性的逻辑漏洞

• 关键问题：Dijkstra 算法在步骤 4 选择并标记顶点 u 时，就永久固定了其最短路径值 d(u)，并宣称“不可能再有更短的路径”。
• 负权边如何打破这个断言：考虑这样一种情况：存在一条更长的、尚未被探索的路径，它先经过某个目前距离较远的顶点 x，然后通过一条负权边从 x 到达 u。这条路径的总长度可能比算法当前找到的 d(u) 更短。
• 具体来说：假设在算法选择 u 时，d(u) = 10。但存在一条路径 源 -> ... -> x -> u，其中 d(x) 当前可能被计算为 12，而边 x -> u 的权重为 -5。那么，通过 x 到 u 的路径总长度为 12 + (-5) = 7，这比 10 更短。然而，由于算法已经标记 u 为已访问，并认为 d(u) 不可更改，它就错过了这条更短的路径。
• 本质原因：在存在负权边的图中，“当前最近的顶点”并不一定是“全局最近的顶点”，因为通过“绕远路”并使用负权边，可能获得更短的总距离。Dijkstra 的贪心策略基于“当前最近”就是“最终最近”的假设，这个假设在有负权边时彻底失效。

5. 使用修正后的示例验证漏洞

让我们稍微修改上面的图，使算法明显出错。

• 修改：将边 B -> D 的权重从 4 改为 1。
• 其他不变：A->B:2, A->C:3, B->C:-1, C->D:2。

再次手动执行 Dijkstra 算法：

1. 初始化：d(A)=0, 其余 ∞。
2. 选择 A，标记已访问。
3. 松弛 A 的邻居：更新 d(B)=2, d(C)=3。
4. 选择 B（距离 2），标记已访问。
5. 松弛 B 的邻居：
   • 检查 C：d'(C)=2+(-1)=1 < 3，更新 d(C)=1。
   • 检查 D：d'(D)=2+1=3 < ∞，更新 d(D)=3。
6. 选择 C（距离 1），标记已访问。
7. 松弛 C 的邻居（D）：
   • 检查 D：d'(D)=1+2=3。3 等于当前 d(D)，不更新。
8. 选择 D（距离 3），标记已访问。

算法结束，d(D)=3，路径为 A -> B -> D，总权重 2+1=3。但请注意，另一条路径 A -> B -> C -> D 的总权重为 2 + (-1) + 2 = 3。两者相等，算法仍得到正确最小值。

让漏洞更明显：再次修改图，引入一条新的、更明显的负权捷径。

• 新图：
  • A -> B: 权重 2
  • A -> C: 权重 4
  • B -> C: 权重 -3 （更大的负权）
  • C -> D: 权重 2
  • B -> D: 权重 10 （很大的正权）

执行 Dijkstra：

1. d(A)=0, 其余 ∞。
2. 选择 A，松弛：d(B)=2, d(C)=4。
3. 选择 B（距离 2），松弛：
   • d'(C)=2+(-3)=-1。-1 < 4，更新 d(C)=-1。
   • d'(D)=2+10=12，更新 d(D)=12。
4. 选择 C（距离 -1），松弛 D：
   • d'(D)=-1+2=1。1 < 12，更新 d(D)=1。
5. 选择 D（距离 1）。

最终 d(D)=1，路径 A -> B -> C -> D，总权重 2 + (-3) + 2 = 1。这次 Dijkstra 看起来又对了。但问题在于：算法依赖于 B 先于 C 被选择，而 C 的新距离 d(C)=-1 是在 B 被处理后才更新出来的。如果图的结构导致算法在更早的阶段就“锁定”了 C 的错误较大值，那么就会出错。

构建一个会出错的最终示例：

• 新图：
  • S (源点) -> A: 权重 2
  • S -> B: 权重 4
  • A -> B: 权重 -3
  • B -> T (目标点): 权重 2
  • A -> T: 权重 5

执行 Dijkstra：

1. d(S)=0, d(A)=∞, d(B)=∞, d(T)=∞。
2. 选择 S，松弛：d(A)=2, d(B)=4。
3. 选择 A（距离 2，小于 B 的 4），标记 A 已访问。至此，算法认为到 A 的最短路径 S->A 长度为 2 已经确定。
4. 松弛 A 的邻居（B 和 T）：
   • 检查 B：d'(B)=2+(-3)=-1。-1 < 4，更新 d(B)=-1。
   • 检查 T：d'(T)=2+5=7，更新 d(T)=7。
5. 选择 B（距离 -1），松弛 T：
   • 检查 T：d'(T)=-1+2=1。1 < 7，更新 d(T)=1。
6. 选择 T（距离 1）。

算法得到 d(T)=1，路径 S -> A -> B -> T，总权重 2 + (-3) + 2 = 1。仍然正确。这引出了一个关键点：在简单的连通图中，Dijkstra 可能通过“侥幸”更新顺序得到正确结果。真正的失效发生在更复杂的图中，当负权边存在于已经确定最短路径的顶点之间，或者当算法必须重新考虑一个已经“定型”的顶点时。标准的 Dijkstra 算法没有机制去“重新打开”一个已标记的顶点。

理论上的确定性失效：考虑一个图，其中存在一个“负权环”（总权重为负的环）。虽然 Dijkstra 算法通常用于无环图讨论，但即使没有环，如果存在一条路径，它通过一个已被算法标记为“已访问” 的顶点 u，然后经过一条负权边到达另一个顶点 v，并且这条路径的总长度小于当前 d(v)，那么算法就会出错。因为它无法再更新 u 或利用 u 去更新 v（如果 u 已处理）。更严谨的数学表述是，Dijkstra 算法正确性证明的一个关键引理是：对于所有边 (u, v)，w(u, v) >= 0。当这个条件被破坏时，证明失效，算法不再具有正确性保证。