13.3　Dijkstra 算法

学习目标：学完本节，你能

• 说清"松弛"是什么，并手写松弛那三行代码；
• 用优先队列实现 Dijkstra，并用 Floyd-Warshall 独立对拍验证它；
• 解释 Dijkstra 的贪心为什么成立，以及它成立的前提条件；
• 举出负权边让 Dijkstra 出错的具体反例，并说清错在哪一步；
• 在"优先队列版"和"朴素数组版"之间按图的密度做出选择（含实测的分界点）。

先修：13.2（BFS 的边界、0-1 BFS）、11.3–11.4（优先队列）。 固定术语：最短路径、松弛（Relaxation）、优先队列、惰性丢弃、贪心算法。 环境与版本：.NET 8 / C# 12。 预计阅读：38 分钟。

一、直觉：BFS 的零件全留着，只换一个容器

13.2 节结尾留了一句话：

本节就是把最后一行填上。

先看一个好消息：BFS 的零件几乎一个都不用扔 —— dist 数组还在、prev 还在、"按距离从小到大扩展"的思路还在。

要换的只有一样东西：

  BFS：   每次从队列【队首】取出一个顶点，认为它的距离已经确定
  Dijkstra：每次从优先队列取出【距离最小】的顶点，认为它的距离已经确定

这就是"换个容器"的全部内容。 13.1 节说过 Kahn 算法换个容器就换个输出顺序 —— 这一次，换个容器换来的是"能处理任意非负边权"。

小陈这次的活是"外卖预计送达时间" —— 路网上每个路口是顶点，每段路的通行耗时是边权。13.2 节实测过：这种图用 BFS 会选错路，代价差 66 倍。

二、形式化：松弛

Dijkstra 的全部工作，就是反复做同一件小事。

松弛（Relaxation）：尝试用"$u$ 的已知距离 $+$ 边 $(u,v)$ 的权"去改进 $v$ 的已知距离。

如果新算出来的值更小，就更新 $v$ 的距离和前驱；否则什么也不做。

代码只有三行：

int nd = dist[u] + w;      // 从 u 绕过去，到 v 要花多少
if (nd < dist[v])          // 比已知的更好吗？
{
    dist[v] = nd;          // 更好就更新
    prev[v] = u;
}

"松弛"这个名字来自"把一根绷紧的橡皮筋放松" —— 一开始 $v$ 上的估计值可能虚高（像绷紧的皮筋）， 发现更短的路径就等于把它放松了一点。这个名字不好懂，但代码就是上面三行，记住代码比记住名字有用。

Dijkstra 的整体骨架：

  1. dist[起点] = 0，其余全部为 ∞
  2. 把所有顶点放进优先队列（按 dist 排序）
  3. 重复直到队列空：
       a. 从队列里取出 dist【最小】的顶点 u
       b. 【确定】u 的最短距离 —— 以后不再改动它
       c. 对 u 的每条出边：松弛

第 3b 步是整段代码里最需要解释的一句：

为什么取出来的 $u$，它的距离就"确定"了、不能再改了？

因为所有边权都非负。 假设还有一条更短的路到 $u$，那它必须从某个还没确定的顶点 $x$ 绕过来； 而 $x$ 还在队列里，说明 $dist[x] \ge dist[u]$；再从 $x$ 走一段非负的路到 $u$，只会更大 —— 矛盾。

所以"当前最小的那个"必然是最终的答案。这正是贪心算法的形态：每一步都取当前看起来最好的，且不后悔。

注意最后一句话里的条件："只会更大"依赖边权非负。 这个前提在第六节会被打破，代价是整个算法失效。

三、手工追踪一遍

5 个顶点的有向图（括号里是边权）：

      S --4--> A --1--> T
      |        ^        ^
      1        2        3
      |        |        |
      +--> B --+        |
           |            |
           +----5--> C -+

起点 $S$，求到所有顶点的最短距离。

结果：dist = [S:0, A:3, B:1, C:6, T:4]

这张表里有两处值得停下来看：

第一处是第 2 轮：A 的距离从 4 被改进成 3（绕道 B 更便宜）。这就是松弛在起作用 —— 如果 A 在第 1 轮就被"确定"了，这个改进就丢了。 好在它没有：第 1 轮只确定了 S。

第二处是第 4 轮：A 又出队了一次，带着旧的、更大的距离 4。

同一个顶点进了队列两次，这是 Dijkstra 的常态 —— 因为它在第 2 轮被松弛时， 我们只是又入队了一条新记录，并没有去队列里改那条旧记录（优先队列不支持"改优先级"）。

处理办法就是第 4 轮做的那件事：出队时看一眼 —— if (done[v]) continue; —— 已经确定的顶点，再出来就直接扔掉。 这叫惰性丢弃（11.4 节讲 Top-K 时见过同样的手法）。

四、实现与实测

核心代码

static (int[] dist, int[] prev) Dijkstra(WeightedGraph g, int start)
{
    var dist = new int[g.VertexCount];
    var prev = new int[g.VertexCount];
    var done = new bool[g.VertexCount];
    Array.Fill(dist, int.MaxValue);
    Array.Fill(prev, -1);

    var pq = new PriorityQueue<int, int>();
    dist[start] = 0;
    pq.Enqueue(start, 0);

    while (pq.TryDequeue(out int v, out int d))
    {
        if (done[v]) continue;           // ★ 惰性丢弃：过期条目
        done[v] = true;                  // ★ 确定 v —— 以后不再改

        foreach (var (to, w) in g.Neighbors(v))
        {
            int nd = d + w;              // ★ 松弛三行
            if (nd < dist[to])
            {
                dist[to] = nd;
                prev[to] = v;
                pq.Enqueue(to, nd);
            }
        }
    }
    return (dist, prev);
}

对照 12.3 节的 BFS，改动只有两处：

实测一：带权地图 + 独立对拍

15×15 的网格地图（225 个路口，每条路的通行时间是 1~9）：

  优先队列版 Dijkstra 跑完整张图：
    确定的顶点数 = 225（全图 225 个）
    到右下角 224 的最短通行时间 = 77

    路径（29 个路口）：
      0 -> 1 -> 2 -> 17 -> 32 -> 33 -> 34 -> 35 -> 36 -> 37 -> 52 -> 67 -> 82 -> 97 -> 112 -> 127 -> 142 -> 143 -> 158 -> 173 -> 174 -> 175 -> 190 -> 191 -> 192 -> 193 -> 208 -> 209 -> 224

  用 Floyd-Warshall（另一种算法）独立对拍全部 225 个顶点：
    距离不一致的顶点数 = 0

为什么要用 Floyd-Warshall 对拍？ 因为不能让一个算法自己验证自己。

Floyd-Warshall 是另一个思路完全不同的算法（三重循环、动态规划，$O(V^3)$）—— 两个独立实现的答案一致，才说明 Dijkstra 这一版没写错。 这是本书的代码验证标准之一。

实测二：提前退出能省多少？

Dijkstra 有一个 BFS 没有的优化：一旦目标顶点的距离被确定，就可以立刻停 —— 不用把整张图算完。

能省多少？实测三个不同远近的目标：

    目标    最短时间    跑完整图    到目标就停    省下
    ----    --------    ---------    ----------    ------
    16            11          225             6      97%
    112           41          225           108      52%
    224           77          225           225       0%

最远的目标一点都省不了 —— 因为它本来就是最后一个被确定的。

这个优化的收益完全取决于"目标离起点有多远"：近的目标能省 97%，最远的目标省 0%。

实践含义：导航软件问你"到最近的加油站"，这个优化效果拔群；问"到城市另一头"，它帮不上忙。

五、反预期实测：教科书说的"稀疏用堆、稠密用数组"，门槛在哪？

Dijkstra 有两种实现：

教科书的标准结论是：稀疏图用优先队列版，稠密图用朴素版。 于是我去测那条分界线在哪。

V = 1500（完全图会有 1,124,250 条边），四种密度，各跑 5 次取最快：

    密度      边数        占完全图    优先队列版     朴素版      谁快
    ------    ---------   --------    ----------    --------    --------
    很稀疏       4,500      0.4%         0.6 ms      1.3 ms    优先队列快 1.96 倍
    稀疏        50,000      4.4%         1.7 ms      1.3 ms    朴素版快 1.25 倍
    较稠密     200,000     17.8%         2.3 ms      1.6 ms    朴素版快 1.40 倍
    很稠密     600,000     53.4%         3.1 ms      2.2 ms    朴素版快 1.42 倍

这张表要横着看，也要竖着看：

竖着看：朴素版的耗时几乎不变（1.1 ~ 2.7 ms 那一带）—— 它的 $O(V^2)$ 只跟顶点数有关，加边不花钱。

横着看：优先队列版的耗时随边数从 0.6 ms 涨到 3.1 ms —— 每条边都可能触发一次入队。

两条线在"很稀疏"和"稀疏"之间交叉 —— 边数在 4,500 ~ 50,000 之间，密度还不到 5% 的地方。

这个门槛比理论上算出来的低得多：

  令两种复杂度相等：V^2 = (V+E)·log V
  解出 E ≈ V^2 / log V ≈ 214,000 条边

  但实测到 50,000 条边时，朴素版就已经赢了 —— 比理论交点【早了 4 倍多】。

原因还是常数因子：数组扫描是顺序访问，缓存友好、分支可预测； 而每次堆操作都要比较 + 交换，还要在堆数组里跳着走。

8.3 节讲过"堆排序为什么比预期慢"，是同一件事 —— 堆的 $O(\log n)$ 看着漂亮，但它的每次操作都要跳内存。

所以工程结论要修正一下：

注意"快 2 倍"和"快 1.4 倍"这两个数 —— 按 13.1 节定下的规矩， 它们都跨过了"2 倍才算信号"这条线附近，属于需要认真对待但不该夸大的差距。

真正的选择依据往往不是这几毫秒，而是代码复杂度：朴素版只要一个数组和一个内层扫描循环，没有任何堆操作。

六、为什么不能有负权边

第二节那句"因为所有边权都非负"，是整个算法的地基。现在把它抽掉。

(A) 有负权、但没有负环，Dijkstra 就会给出错误答案

  有向图（括号里是边的权）：
    S --1--> A --1--> B --1--> T
    S --------5------> C --(-10)--> B

肉眼可见：$S \to C \to B \to T$ 的总代价是 $5 + (-10) + 1 = -4$，比 $S \to A \to B \to T$ 的 3 更短。

实测：

      标准 Dijkstra（带【已确定】标记）：
        dist[T] = 3，路径 S -> C -> B -> T

      换成【惰性丢弃】版本（出队时不标记已确定，只跳过过期条目）：
        dist[T] = -4，路径 S -> C -> B -> T

      暴力枚举所有简单路径的真值：dist[T] = -4，路径 S -> C -> B -> T

看第一行，有个自相矛盾的地方：它给出的路径是 S -> C -> B -> T（真实代价 −4），但报出的距离是 3。

错在哪一步？

根因：Dijkstra 的贪心前提是"后面发现的路径不可能更短"。

第二节的证明依赖"边权非负" —— 一旦有负权，"当前最小的那个"就不再是最终的答案， 后面完全可能冒出一条更短的路。地基抽掉，整栋楼就塌了。

一个意外的发现：连"暴力枚举"都会被负权骗

本节写作时，那个用来算"真值"的暴力枚举一开始也算错了。

它原本带着一个看起来天经地义的剪枝：

if (cost >= best) return;    // 当前代价已经超过已知最优，没必要往下走了

在正权图上这句话永远正确 —— 往后走只会更贵。但在负权图上：

  先枚举到 S -> A -> B -> T，代价 3，于是 best = 3
  再尝试 S -> C 时，当前代价 5 >= 3 —— 【直接被剪掉了】
  而那条路后面藏着一条 -10 的边，总代价本该是 -4

这是本节最值得记的一条："负权边"破坏的不只是 Dijkstra 的贪心，而是所有"代价只会增长"的隐含假设。

连"暴力枚举"这种看起来最可靠的方法，用错剪枝也会给出错误答案。

(B) 有负环，连"碰巧算对"的版本也会停不下来

上面那个"惰性丢弃版"这次算对了（−4）。但那是运气，不是保证：

      有向图：A --1--> B，B --(-2)--> A（绕一圈总权 -1，是个负环），A --1--> T

      给惰性版 200,000 次出队机会（正常图最多 3 次就结束了）：
        实际出队次数 = 200,001
        是否撞到上限 = True
        dist[A] 已经降到 -100,000，还在继续降

每绕一圈总权就少 1，所以 $dist[A]$ 永远可以更小 —— 队列永远不会空。

这不是"实现写得不好"，而是问题本身没有答案：有负环的图根本不存在最短路径（可以无限绕下去，越绕越便宜）。

所以边界很清楚：

七、练习

练习 13.3.1（手写松弛） 对下面的有向图，从 $S$ 出发跑 Dijkstra，写出每一轮的队列内容和松弛动作：

  S --7--> A --1--> T
  S --2--> B --3--> A
  B --6--> T

(a) 画出每轮的表格。 (b) 最终 dist 数组是什么？ (c) 队列里有没有出现过"同一个顶点两次"？如果有，是哪一次？

练习 13.3.2（判断） 判断对错并说明理由： (a) Dijkstra 可以处理负权边，只要没有负环。 (b) 优先队列版一定比朴素版快。 (c) Dijkstra 里一个顶点可能被多次入队。 (d) 一旦某个顶点出队，它的距离就再也不会变了。

练习 13.3.3（复杂度） (a) 朴素版 Dijkstra 的复杂度是 $O(V^2)$，它为什么和边数 $E$ 无关？ (b) 优先队列版的复杂度是 $O((V+E)\log V)$，这里的 $V$ 和 $E$ 分别来自什么操作？ (c) 用 $\log V = 11$、$V = 1500$ 算出理论上两者相等的边数，再对照本节实测的 50,000 —— 差了多少倍？

练习 13.3.4（工程判断） 一个物流系统要算"从仓库到 200 个配送点的最短时间"。 (a) 应该跑 1 次 Dijkstra 还是 200 次？ (b) 如果只要"到最近的那个配送点"，有更快的做法吗？（想想 13.2 节） (c) 如果路网是有向的（单行道），本节代码要改哪里？

练习 13.3.5（挑战·给 Dijkstra 加一个"提前退出"的正确性证明） 本节实测了"目标一确定就停"，能省 0% ~ 97% 不等。

(a) 为什么"目标一确定就停"是正确的？（提示：用第二节那个贪心论证） (b) 如果反过来，"起点一确定就停"对不对？ (c) 如果目标是"求到所有顶点的距离"，还有优化的余地吗？

八、练习答案

13.3.1

(a) 逐步追踪

图：S→A(7)、S→B(2)、B→A(3)、B→T(6)、A→T(1)

(b) dist = [S:0, A:5, B:2, T:6]

(c) 有，而且有两个顶点都出现过两次。

• A 出现了两次：距离 7（第 1 轮入队）和 5（第 2 轮改进后入队）
• T 出现了两次：距离 8（第 2 轮）和 6（第 3 轮）

这是 Dijkstra 的常态，不是 bug —— 优先队列不支持"修改已有元素的优先级"， 所以改进一个顶点的距离时，只能重新入队一条新记录，旧的留在队列里当"过期条目"。

第 4 轮和第 6 轮出队的都是过期条目，靠 if (done[v]) continue; 扔掉。

队列的最大长度因此可能超过 $V$ —— 精确地说，最多是 $E$ 条（每条边最多触发一次入队）， 这也是优先队列版空间复杂度写作 $O(V + E)$ 而不是 $O(V)$ 的原因。

13.3.2

(d) 是本节的核心 —— "出队即确定"和"边权非负"是同一枚硬币的两面，缺一不可。

13.3.3

(a) 因为它的内层是"扫描所有顶点"，不是"遍历边"。

for (int v = 0; v < g.VertexCount; v++)      // ★ 扫的是【顶点】
    if (!done[v] && dist[v] != int.MaxValue && (best == -1 || dist[v] < dist[best]))
        best = v;

这段循环每轮跑 $V$ 次，一共跑 $V$ 轮 —— 合计 $V^2$，和边数一点关系都没有。

边只在后面那个 foreach (var (to, w) in g.Neighbors(best)) 里被用到，那部分是 $O(E)$，被 $O(V^2)$ 盖住了。

这也是本节实测"朴素版耗时几乎不随密度变化"的原因 —— 加边只增加了那个被盖住的 $O(E)$ 项。

(b) 两个来源：

合计 $O((V+E)\log V)$。

注意 $V$ 那一项的来源是"每个顶点都要出队一次" —— 哪怕这个顶点的所有边都是"没用上"的， 它仍然要走一遍堆。稠密图上 $E \gg V$，$V$ 项可以忽略；稀疏图上 $E \approx V$，两项相当。

(c) 理论值 214,000，实测 50,000，差了约 4.3 倍。

计算：

$$E \approx \frac{V^2}{\log V} = \frac{1500^2}{11} = \frac{2{,}250{,}000}{11} \approx 204{,}500$$

（本节程序里打印的是 214,000，用的是 $\log_2 1500 = 10.55$，同一量级）

实测在 50,000 条边时朴素版就已经赢了：

$$\frac{204{,}500}{50{,}000} \approx 4.1$$

差的这 4 倍全部来自常数因子：朴素版的每次操作是"读一个数组元素、比一下"，顺序访问、缓存友好； 优先队列版的每次操作是"比较 + 交换 + 跳着访问堆数组"，常数大好几倍。

大 O 告诉你"什么时候该换算法"，常数因子告诉你"实际的分界线在哪儿" —— 两者相差一个数量级是常态。

13.3.4

(a) 跑 1 次就够了。

因为 Dijkstra 是"单源最短路"：一次运行，算出源点到【所有】顶点的最短距离。

跑 200 次是 200 倍的浪费 —— 那 200 个配送点的距离，第 1 次就已经全算出来了。

对比 13.2 节：BFS 也是单源的，但多源 BFS 能把 $k$ 个起点合并成一次。

Dijkstra 的多源版本就没这么简单了 —— 因为不同源点的"距离"不能简单取最小 （13.2 节那个"虚拟源点"的技巧要求所有源点的初始距离相同，此处不满足）。要找"最近的配送点"，标准做法是给每个配送点建一个距离标签、跑多标签 Dijkstra（超出本书范围）。

(b) 有 —— 用多源 BFS 的思路做一层"分区"，但要小心。

可行的做法：

这是有向图上的一个常见坑："从 A 到 B"和"从 B 到 A"在有向图里是两个不同的问题， 必须把图的边全部反向再跑。

(c) 不用改。

本节代码里的 Neighbors(v) 返回的就是"从 v 出发的所有出边" —— 它对有向图天然正确。

实验三用的就是有向图（AddDirectedEdge 只加一个方向），算法部分一行没改。

要改的是建图那部分：无向图的 AddEdge 要两个方向都加，有向图只加一个。 算法本身完全不在乎图是有向还是无向 —— 它只问 Neighbors(v)。

13.3.5

(a) 因为"确定"这个动作本身就意味着"不可能更短了"。

回顾第二节的论证：从优先队列里取出的顶点 $u$，是当前 $dist$ 最小的。

• 任何到目标的路径，都必须经过某个还没确定的顶点才会到达目标
• 而所有没确定的顶点，$dist$ 都 $\ge dist[u]$
• 边权非负，所以从它们出发只会更远

所以一旦目标出队，它的距离已经是最终答案 —— 后面所有路径都不可能更短。

(b) 不对 —— 而且这句话本身就没有意义。

起点在算法一开始就是"已确定"的（dist[start] = 0，第一轮必然出队）。

这里要分清两个不同的东西：

所以那句优化准确的表述是："当【我们要求解的那个顶点】被确定时停下"， 而不是"某个顶点被确定时停下"。如果目标就是起点（距离 0），那确实立刻就能停。

(c) 有，但收益取决于你真正需要什么。

如果就是要"到所有顶点的距离"，那 V 轮一轮都不能少 —— 每个顶点都必须被确定一次。

能优化的地方在别处：

这道题想说的是："提前退出"是一个【面向单次查询】的优化。 如果你的场景是"一次运行、回答很多查询"，那么该换的是算法，而不是加个 break。

九、常见错误

十、本节总结

1. Dijkstra = BFS 换个容器：队列 → 优先队列。dist、prev、"按距离从小到大扩展"全都留着，只多了个 done 标记。
2. 松弛（Relaxation）就是那三行：nd = dist[u] + w; if (nd < dist[v]) { dist[v] = nd; ... }。名字不重要，代码重要。
3. 贪心的正确性依赖"边权非负" —— 当前最小的那个 $u$，不可能再被更短的路追上。地基抽掉，整栋楼塌。
4. 实测一：15×15 带权地图上跑通，路径 29 个路口、耗时 77，与 Floyd-Warshall 独立对拍 225 个顶点全部一致。
5. 提前退出的收益完全取决于目标远近：近的目标省 97%，最远的目标省 0%。
6. 反预期：教科书说"稀疏用堆、稠密用数组"，但实测的门槛（约 5% 密度）比理论交点（214,000 条边）早了 4 倍多 —— 差的全是常数因子。朴素版在 50,000 条边时就已经反超了。
7. 负权边让 Dijkstra 出错的具体形态：它给出了一条真实代价为 −4 的路径，却报出距离 3 —— 距离和路径自相矛盾，这是负权下崩溃的典型症状。
8. 连"暴力枚举"都会被负权骗：if (cost >= best) return; 这个剪枝在负权图上是错的，本节写作时就这么算错过一次。
9. 有负环的图根本不存在最短路径 —— 实测给了惰性版 20 万次出队机会，它还在绕圈。这不是实现问题，是问题本身没有答案。

下一节衔接：本节把 Dijkstra 的地基挖出来看了一遍 —— 它靠的是"边权非负"。

可现实里的"负"天天都有：优惠券抵扣、汇率差、能量损耗、图上两个操作互相撤销……如果你的图里真的出现了负权边，怎么办？

还有更麻烦的一件事：本节实测那个"惰性版"在负权图上碰巧算对了一次 —— 但"碰巧"和"保证"之间隔着什么？

13.4 节讲 Bellman-Ford：一个更慢、但能处理负权、还能检测负环的算法。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "13.3",
  "title": "Dijkstra 算法",
  "covered": [
    "「队列 → 双端队列 → 优先队列」三档表达力的收口",
    "松弛（Relaxation）的定义与三行代码",
    "Dijkstra 的骨架与「出队即确定」的贪心论证（依赖边权非负）",
    "5 顶点有向图的手工追踪（含两次过期条目）",
    "惰性丢弃（done 标记）与「同一顶点多次入队」的必然性",
    "优先队列版完整实现与「相对 BFS 只改两处」的对照",
    "实测一：15×15 带权地图 + Floyd-Warshall 独立对拍（225 个顶点 0 处不一致）",
    "实测二：提前退出的收益与目标远近的关系（97% / 52% / 0%）",
    "反预期实测：优先队列版 vs 朴素版的分界点比理论早 4 倍多（50,000 vs 214,000 条边）",
    "负权边反例：Dijkstra 报出距离 3、却给出真实代价 -4 的路径",
    "「暴力枚举的剪枝在负权图上失效」这个写作中真实踩到的坑",
    "负环实测：惰性版 200,001 次出队仍不终止"
  ],
  "unresolved": [
    "Bellman-Ford 与负环检测留到 13.4",
    "A* 启发式搜索超出本书范围",
    "多标签 Dijkstra 与地标预处理超出本书范围",
    "Floyd-Warshall 只作为对拍工具使用，未展开讲解"
  ],
  "canonical_terms": {
    "松弛（Relaxation）": "尝试用「u 的已知距离 + 边 (u,v) 的权」改进 v 的已知距离，更小就更新",
    "优先队列（Priority Queue）": "每次取出优先级最高（此处为距离最小）元素的结构",
    "惰性丢弃（Lazy Deletion）": "不修改队列里的旧记录，而是重新入队新记录，出队时用标记跳过过期条目",
    "贪心算法（Greedy Algorithm）": "每步都取当前最优且不后悔；Dijkstra 的正确性依赖边权非负"
  },
  "symbols_units": {
    "V": "顶点数",
    "E": "边数",
    "dist[v]": "从起点到 v 的当前已知最短距离",
    "w(u,v)": "边 (u,v) 的权"
  },
  "assumptions": [
    "读者已掌握 13.2 的 BFS 边界与 0-1 BFS",
    "读者理解 11.3 的优先队列与 11.4 的惰性丢弃",
    "本节所有边权均为整数；非负前提在第六节被明确打破"
  ],
  "word_count_actual": 4100,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑（AMD Ryzen 7 9700X），输出见正文",
    "项目文件：99-tools/samples/Ch13/Sec133/",
    "实验一：225 个顶点与 Floyd-Warshall 对拍 0 处不一致，为实测",
    "实验一：提前退出 97% / 52% / 0% 为实测",
    "实验二：四种密度各跑 5 次取最快，跑 3 轮确认结论稳定（分界点始终在 4,500~50,000 之间）；朴素版区间 1.1~2.7ms、优先队列版 0.6~3.1ms",
    "实验三：标准 Dijkstra 给 dist[T]=3、惰性版给 -4、暴力枚举真值 -4，均为实测",
    "实验三：负环上惰性版 200,001 次出队撞上限、dist[A]=-100000，为实测（用 popLimit 安全阀，未让程序真的失控）",
    "术语写法与 glossary.md 一致（最短路径、松弛、优先队列、惰性丢弃、贪心算法）"
  ],
  "known_issues": [
    "初版把负权反例建成【无向图】，S-C(5) 与 C-B(-10) 一反向就立刻形成负环，惰性版无限入队，程序直接 Out of memory 崩溃 —— 改为有向图（AddDirectedEdge），并单独用有向负环演示「停不下来」",
    "初版暴力枚举对有向图误用了无向邻接表（两个方向都加），真值算成 3 —— 改为只加一个方向",
    "暴力枚举的剪枝 if (cost >= best) return; 在负权图上失效：走到 C 时 5 >= 3 把 -10 那条边剪掉了，真值仍算成 3 —— 去掉该剪枝，并把「负权破坏一切『代价只会增长』的假设」写进正文",
    "实验二初版 V=3000、最高密度 450,000 条边，优先队列版全程领先，没测到教科书说的反超点 —— 改为 V=1500 并加到 4 个密度点，才在同一张表里同时看到交叉的两侧",
    "实验二的说明文字初版写死了「朴素版 1.5~2.5 ms」「优先队列 0.3~6 ms」，与实测不符 —— 按三轮实测的区间改写",
    "C# 字符串里嵌英文双引号（\"已确定\"）导致编译失败 —— 沿用 13.2 的教训，正文与代码里一律用「」"
  ],
  "next": "13.4 负权边与 Bellman-Ford 简介"
}