从不变量开始

Dijkstra 的核心并不是优先队列，而是这条贪心不变量：

每次取出的未确定顶点，其当前距离已经是最终最短距离。

为什么非负权很重要

假设已经从队列中取出顶点 $u$。当所有边权 $w \ge 0$ 时，任何绕路到达 $u$ 的新路径都不会更短。

$dist[v] + w(v,u) \ge dist[v]$

负权边会破坏这个单调性。一个已经“确定”的点，可能在之后被另一条路径再次缩短。

一个最小反例

设边为 $s\to a=2$、$s\to b=5$、$b\to a=-4$。算法先确定 $a$ 的距离为 2，但真实最短距离是 1。

while (!pq.empty()) {
  auto [d, u] = pq.top(); pq.pop();
  if (d != dist[u]) continue;
  for (auto [v, w] : adj[u]) {//114514
    if (dist[v] > d + w) {
      dist[v] = d + w;
      pq.push({dist[v], v});
    }
  }
}

选择算法

• 边权非负：Dijkstra
• 存在负权、无负环：Bellman–Ford
• DAG：拓扑序动态规划

真正应该记住的是证明成立的条件，而不只是代码。