先修：01 模型、目标与假设；02 命题与条件；03 图、路径与可达性；04 循环不变量与终止性
程序给出一条从S到T的路线，标着“6分钟”。沿路加一遍，确实是6分钟。这能证明它走得通，也能证明总数没加错。可是，别处会不会藏着一条5分钟的路？
第一章的五站地图很小，我们把两条不重复站点的路线全列出来，就能比较。图大了以后，路线数量可能多得难以逐条检查。这一章要找一种办法：一边计算，一边积累足够的理由，最后能说清楚，为什么更短的路线已经被排除了。
先给答案划定范围
仍用那五个虚构站点：S—A、A—T各需4分钟；S—B、B—C、C—T各需2分钟。所有连接允许双向通行。本章回到只算行车时间的版本，暂不计换乘和候车，因此两条路线分别是8分钟和6分钟。
接下来的方法还适用于更一般的图，但输入要满足几项约定：节点与边的数量有限，起点S在图中，每条边的权重都是固定、有限的非负数，计算期间图不变。非负允许0；如果边有方向，就只能顺箭头走。双向连接也可以看成两条反向、等权的有向边。
本章的“最短”指边权之和最小，也称代价最小；它不再专指第三章数过的边数。如果每条边都用相同的正数计价，少走一条就少付相同代价，按边数一层层扩展就能解决。眼前有2分钟和4分钟两种边，单看层数不够。
沿用第三章的约定，路径不重复节点。有限图中的路径只有有限多条，终点只要可达，就能从中挑出总代价最小的一条。如果允许绕圈，删掉一段绕行也不会增加代价，因为被删去的边权都非负。因此，限制为不重复节点，不会漏掉更便宜的答案。不可达的终点则没有这样一条路径。
给每个站放一张可以改的便签
先给每个节点v记录一个数d(v)，叫作暂定距离。
d(S)＝0，因为留在起点无须经过任何边。其他节点先记为∞，读作“无穷大”。这里的∞是“还没找到路线”的标记，比任何有限代价都大，不能读成“已经证明到不了”。
一旦d(v)变成有限数，它就必须对应一条已经找到的、从S到v的路线。比如d(T)＝8，意思是“现在有一条8分钟的路线可用”。真正的最短时间不会大于8，所以暂定距离是最短时间的一个上界；它仍可能被更好的路线降低。
另外准备一个已确认集合K，起初为空。放进K的节点，距离将被当作最终答案，之后不再修改。暂定距离与最终距离的区别，正是算法需要证明的地方。
现在反复做同一组动作：
- 从尚未确认的节点里，挑d值最小且有限的一个，记为u。并列时任选一个
- 把u加入K，确认它的距离
- 检查u指向的每个尚未确认的邻居v。若d(u)加上这条边的权重，比d(v)更小，就更新d(v)，并记下这次到达v的前一站是u
- 如果所有节点都已确认，或剩下的d值全为∞，就停止；否则回到第一步
第三步叫作松弛。设u→v这条边的权重为w(u,v)，它比较的就是d(v)与d(u)＋w(u,v)。只有严格变小时才更新，相等则保留原记录。新值来自“已有路线接上一条边”，仍然有一条具体路线作为依据。这些是Dijkstra算法的基本操作。1
先不用学习新的数据结构。站点少时，每轮把尚未确认的便签扫一遍，就能找出最小值。
五个站点，走完一次
初始化以后，只有S的便签是有限数，所以先确认S，再沿它的两条连接，把A写成4、B写成2。
接着确认B。经过B去C，要2＋2＝4分钟，于是C从∞变成4。现在A与C并列，便签都是4。我们先选A，沿A到T这条边，得到4＋4＝8，T的便签第一次有了有限数。
这时不能因为“已经看见终点”就停下。C还没确认，暂定距离只有4，比T的8小。下一轮确认C，经过它去T只需4＋2＝6分钟，T的便签于是从8改成6。
最后确认T，答案定为6。
图1：每行记录该轮确认与松弛全部完成后的状态。蓝底数值已确认，橙底数值是本轮新写入或降低的暂定距离。
更新便签时保留的“前一站”，还能把完整路线找回来：T记着C，C记着B，B记着S。逆着这些记录回到起点，再把顺序翻转，就得到S→B→C→T。
这些前一站都在当前节点之前得到确认，沿记录倒着走，确认次序会严格提前，因此不会困在一个圈里。记录距离与记录路线，在这里彼此对应。
如果刚才并列时先选C，T会直接写成6，不会经历8这个中间值。确认顺序和过程记录可以不同，最终距离仍相同。存在多条同样短的路径时，本章只要求返回其中一条。
为什么最小的便签可以定型
手算还没有回答最关键的问题：便签只是“目前找到的最好路线”，凭什么最小的那张，能升级成“所有路线里最好”？
接上上一章的不变量。我们希望每轮开始时，K里每个节点的距离都已经正确；每个有限的d值都有已找到的路线支撑；K中节点通往外面的边也都已经检查过。
第一次选中的是S。零步路线代价为0，非负边组成的任何游走都不可能比0更小，所以确认S是安全的。检查完S的邻边，上面的承诺就成立了。
现在假设此前确认的节点都正确。这一轮选中了u，且d(u)是未确认节点中的最小值。随便拿一条从S到u的路径P，看看它有没有可能比d(u)更便宜。
S已经在K中，u还在外面。因此，顺着P走，必定会遇到第一个不在K中的节点，叫它y；y的前一个节点叫x，必定在K中。y也可能就是u。
图2：这是一条任意路径P的示意。蓝色部分到达边界外的第一个节点y；后续怎么绕，都必须继续支付非负代价。
沿着这条路径，可以核对三件事。
第一，y的便签不会大于P走到y时已经花掉的代价。 因为x的距离已经正确，d(x)不会比P的前半段到x更贵。x得到确认时，算法又检查过x→y，拿d(x)＋w(x,y)与y的旧值比较，保留较小值。因此，d(y)不大于P从S到y的代价。此后便签只会降低，这个不等式一直保留。
第二，u的便签不大于y的便签。 y还没确认，u是所有未确认节点中d值最小的一个，所以d(u)≤d(y)。哪怕并列，这句话也成立。
第三，P走到y的代价不大于走完整条P的代价。 剩下的每条边都非负，继续走不会让累计代价下降。这里用到了本章最重要的输入条件。
把三件事接起来：
d(u) ≤ d(y) ≤ P从S到y的代价 ≤ P的总代价。
也就是说，无论拿哪条到u的路径来挑战，它都不会比d(u)更便宜。同时，d(u)本身又有一条实际找到的路线作为依据。于是这个值确实能够达到，也没有路径能低于它，确认u是安全的。2
确认后，再检查u的邻边，就恢复了下一轮需要的全部承诺。初始化正确，每轮又能把正确性传给下一个节点，这正是上一章的不变量与归纳推理。我们把路径P留成任意一条，才一次覆盖了所有竞争路线。
这也说明，只求到T的答案时，可以在T被选中确认后停止。第一次给T写上有限数，尚未获得这份保证。
停下来以后，∞又是什么意思
每轮都会确认一个新节点，已确认的节点不再退出。若图有n个节点，剩余节点数就是一个非负整数，每轮严格减少1，因此最多确认n次。每次扫描和检查邻边也只涉及有限个对象，算法必定结束。
这里讨论按原流程完成全部搜索的情况，而不是确认T后提前停止。如果此时还有节点的d值为∞，就能证明它们不可达。
假设其中某个节点其实可达，拿一条到它的路径，照刚才的办法，找路径上第一个尚未确认的节点y。它的前一站x已经确认；检查x的邻边时，y就应获得有限值。这与“剩余便签全是∞”矛盾。因此不会漏下可达节点。
∞在初始化时只表示还不知道，经过完整的搜索以后，才有了不可达的结论。程序里的同一个符号，必须连同它所处的阶段一起理解。
放进一条负边，哪一步断了
把地图暂时换成三个节点的有向图：S→A的权重是1，S→B是2，B→A是−3。这里的数字表示一般代价，不解释为地铁行车时间。
确认S后，A的便签为1，B为2。按刚才的规则，A先被确认，距离定为1。可另一条路径S→B→A的总代价是2＋(−3)＝−1，比1更小。
图3：负边让较贵的前半程，在补上后半程以后反而更便宜。“先确认A为1”的结论因此失效。
对照证明，P走到B时花了2，走完整条路径却只花−1。“前半段代价不大于全程代价”不再成立，最小便签就失去了提前定型的依据。
这个图没有有向环，当然也没有负环；最短路径完全存在。反例说明的是：本章这种确认后不再修改的Dijkstra过程，不能保证处理负边时仍然正确。负边与负环是两种条件，不能混为一谈。零权边则不破坏证明，因为它不会让累计代价下降，仍然满足我们使用的≤关系。3
证明保证了什么，速度又取决于什么
到这里，6分钟已经带着一个清楚的保证：在这张有限、静态、非负边权的图上，没有更便宜的路线。它没有自动计入第一章那5分钟换乘，也没有预知下一班车什么时候到。把模型补完整以后，还要重新检查这些前提。
“答案正确”与“程序多久算完”也各有问题要回答。我们用全扫描挑下一站，每次最多看n个节点，最多挑n次，仅这部分就至多查看n²个便签。更合适的数据结构可以减少这项工作；它改变找最小值的效率，并不替代上面的正确性理由。3
如果AI生成了一段寻路程序，可以从三个具体问题开始审查：有限距离是否都有路线依据？它是在发现终点时退出，还是确认终点后退出？输入是否允许负边？这些检查直接对应证明里承担责任的步骤。
最短路让我们看到一种可复用的思路：先找到一条能达到的路线，再利用所有路线都绕不开的边界，证明没有路线能更便宜。答案的数值与排除其他可能的理由，在同一轮轮计算中逐渐会合。
顺手试一下
题目1：并列以后，记录会怎样变
把五站图中的C—T改成4分钟，其余不变。仍然在A与C并列时先确认A。T先得到多少？检查C—T时要不要更新？最终最短路径是否唯一？
**提示：**比较经过A的4＋4与经过C的4＋4，并留意算法只在严格变小时更新。
**参考答案：**T先得到8。检查C—T时仍是8，所以不更新，保留前一站A，返回S→A→T。但S→B→C→T也恰好是8分钟，最短路径不唯一；算法只保证返回其中一条。
题目2：0和∞分别说了什么
在原五站图中把B—C改成0分钟，再增加一个没有任何连接的节点U。从S出发，C与T的最短时间各是多少？仅凭算法的记录，U的∞何时能解释为不可达？
**提示：**0分钟边仍然是一条边。对U，则区分搜索刚开始与所有有限便签都已确认的时刻。
**参考答案：**C为2＋0＝2分钟，T为2＋0＋2＝4分钟，算法仍然适用。U初始化时的∞只表示尚未找到路线；算法完整结束后仍为∞，结合搜索已覆盖全部可达节点的理由，可以把它判为不可达。题目还给了U没有任何连接这个条件，也能据此直接判断；单看初始化的∞则不行。
延伸阅读与来源
- Robert Sedgewick、Kevin Wayne，《Algorithms, 4th Edition》配套材料第4.4节：Shortest Paths。核对暂定距离的初始化、边松弛和前驱边记录。本章五站手算沿用第01章的虚构模型。
- Cornell CS 2110，Dijkstra’s Algorithm，2011年夏季讲义。核对“已有路线给出上界”与路径跨越已确认集合边界的正确性论证；本文用任意竞争路径重述这段推理。
- MIT 6.006，Lecture 13: Dijkstra’s Algorithm，2020年春季讲义。核对非负边权在证明中的作用，以及数组扫描与其他数据结构的运行成本区别。本文不要求预先了解优先队列，三节点负边反例为本文自设。
作者：Jiancheng Wang · 数学之美（独立原创）