从起点到一个顶点的当前最好路径，未必已经是最短路径。Dijkstra能永久确定当前距离最小的顶点，是因为后面的非负边不能把尚未发现的路径变得更短。允许负边以后，这项推理失效，优先队列本身无法补回缺失的前提。

本篇在同一个有向图接口上比较Dijkstra与Bellman–Ford，再用势函数说明怎样在保留路径比较的条件下消除负边。09篇的索引堆继续用于减键，22篇的状态依赖思想用于理解有边数限制的路径。

距离与路径证据

输入n≥1个顶点、m条有向整数权边以及起点s。顶点编号0到n−1，平行边和自环保留独立输入ID。输出每个顶点的距离和前驱边ID；不可达顶点距离为None，不能用一个可能被真实路径超过的有限大整数冒充无穷。

Dijkstra要求全图边权非负，发现负权就拒绝，即使负边位于当前起点不可达的分量。Bellman–Ford允许负边，但只在存在从s可达的负环时报告异常，并给出一个可核对的环。异常时不把尚在变化的距离数组作为最终最短距离交付。

没有可达负环时，任意最短路都可去掉非负环，得到至多n−1条边的简单路径。若某个负环可达，能通过它到达的顶点可以反复绕环降低路径权重，因此不存在有限最小值；图中其他不可达负环则不影响本次源点查询。

松弛保持真实路径上界

初始化d[s]=0，其余不可达。对边u→v，若u已可达且d[u]+w小于d[v]，就替换d[v]并记下这条前驱边。每个有限标签都来自一条实际游走，所以不会低于真正的最短值；松弛只是寻找更好的上界。

这个不变量不足以决定何时停止。Dijkstra增加“永久确定”的证明，Bellman–Ford则利用路径边数和全边扫描判断是否仍可改善。两者可以共用松弛含义，不能共用未经核查的终止条件。

非负性如何证明最小标签安全

设u是尚未确定的顶点中标签最小者。取一条到u的最短路径，沿路径找第一个未确定顶点y，其前驱x已经确定。处理x的出边后，d[y]不大于这条路径到y的前缀权重。

由于后续边非负，这个前缀权重不大于到u的最短距离。又因为u的标签最小，d[u]≤d[y]。结合标签本来就是真实路径上界，得到d[u]等于最短距离，可以永久确定。

若边为s→a权2、s→b权5、b→a权−4，算法会先确定a为2，但真实最短路s→b→a只有1。问题正出在“前缀不大于整条路径”这一步。允许已确定节点不断重新入队会变成另一种算法，不能保留原Dijkstra证明与复杂度。

实现复用09篇IndexedHeap，每个未确定且已发现顶点只保留一个堆条目。新顶点插入，已在堆中的顶点发生严格改善则减键；出堆在证明中表示永久确定。程序不另存确定标记：非负性保证这个顶点以后不会再被严格改善，因此不会对已经离堆的ID执行减键。

建邻接表O(n+m)，至多n次插入与出堆、m次减键，堆比较和移动计O((n+m) log(n+1))。完整Python实现还沿用09篇字典定位的期望常数假设与列表追加的摊还成本，不能把它称为解释器端到端确定性最坏延迟；也未给出高概率尾界。

Bellman–Ford为何最多需要这些轮次

可以先把D_t[v]定义为使用至多t条边到达v的最短距离。它来自上一层的原值，或某条入边u→v对应D_(t−1)[u]+w。没有可达负环时，n−1层已经覆盖一条简单最短路径。

教学程序每轮原地扫描全部边，后面的边可能立即使用本轮刚改进的标签，因此一轮可能传播多条边。它不逐项等于“恰好只多一条边”的分层表，但至少覆盖每轮增加一条边的所有路径，并仍保持真实路径上界。因此无可达负环时，n−1轮后所有可达距离必然正确。

若某轮完全没有改善，所有可达边都满足d[v]≤d[u]+w，可提前停止。若第n轮仍有严格改善，则不可能处于无可达负环情形，需要报告负环。算法只从有限标签出发松弛，不可达负环不会触发这一条件。

最坏扫描O(nm)次边，连同长度n数组初始化为O(n+nm)，空间O(n+m)。空边图也需要输出n个距离，不把m=0代入乘积后声称零成本。这是确定性最坏工作量，没有随机成功率。

前驱边把负环变成可核对结果

第n轮记录一个被更新的顶点，沿前驱边反向追n步进入某个前驱环，再继续追到重复顶点。得到的边序列反转后按有向边方向排列。必须保存边ID而不只保存前驱顶点，否则平行边可能对应不同权重，无法明确检验环的总权重。

检查证书时，验证首尾相接、每条边确实属于输入、总权重为负，并验证该环从s可达。有限随机图上输出一个看似成环的顶点列表，不足以证明它是负环；这些性质需要逐项核对。

正常返回时也验证前驱链：到达s、没有循环、边方向正确，权重和等于报告距离。最优性则由算法证明与独立最短路参照共同检查，不把“能恢复一条路径”当成已经证明最短。

势函数怎样保留路径比较

选势h(v)，定义重赋权

w′(u,v)=w(u,v)+h(u)−h(v).w'(u,v)=w(u,v)+h(u)-h(v).

路径内部势项相消，因此从s到t的任意路径满足w’(P)=w(P)+h(s)−h(t)。相同端点的所有路径都加上同一个常数，大小顺序不变。不同终点之间的距离比较不能直接照搬，因为修正常数不同。

加一个超级源，向每个原顶点连权0边，再运行Bellman–Ford。若无负环，取h(v)为超级源到v的距离；三角不等式h(v)≤h(u)+w(u,v)给出w’≥0。随后可对重赋权图运行Dijkstra，并用d(s,t)=d’(s,t)−h(s)+h(t)恢复距离。

超级源使所有顶点可达，因而能检测全图任意负环；只从某个普通源得到的势不能给不可达顶点自动提供有限值。若存在负环，环上势项仍相消，无法让它的每条边都非负，所以不能靠任选一个势绕过负环。

本篇用这一关系验证重赋权，不实现完整多源服务或宣称某个全对最短路性能。不同讲义可能令势等于上述h的相反数，公式符号必须整体转换。

可复跑检查

教学实现位于examples/advanced-algorithms/shortest_paths.py，从仓库根目录运行：

1
python3 examples/advanced-algorithms/check_shortest_paths.py

独立参照使用Floyd–Warshall距离矩阵，不调用上述两种算法。它通过从源点可达且对角距离为负的顶点判断可达负环；正常结果还逐条核对前驱路径，异常结果核对负环证书。

本次实际运行通过512个小图与源点组合，其中254例存在可达负环；固定种子20260920的300个随机图中有136例可达负环。另通过4个边界例、8个非法输入拒绝，以及50张无环图上的250个重赋权源点检查。完整输出保存于examples/advanced-algorithms/results/shortest_paths.json。

这些是有限输入上的教学实现检查，不是图规模的一般证明，也没有测量运行时间。整数加法、比较按单位成本分析；Python大整数位数增长后的实际成本不包含在上述图操作计数里。

练习

  1. 对负边反例，逐步列出永久确定版Dijkstra和Bellman–Ford的标签变化。将b→a的权重改为−3时，为什么一次得到正确答案仍不能证明该负权输入类别普遍安全？
  2. 给定势h，证明任意有向环的重赋权总和不变。由此说明存在负环时，不可能得到全部非负的重赋权边。

参考资料