Johnson 全源最短路算法

势函数给每个顶点换一个高度零点。单条边的坡度随两端高度改变，但一条完整路径的变化只由起终点决定；所以可以消除局部负边，而不改变同一对端点之间的路径排名。非负新权让 Dijkstra 可用，最后再撤销端点偏移。

Bellman–Ford 不只是预处理负边，它同时生成保证非负性的可行势，并充当负环证书。随意选择 $h$ 可能仍留下负边，使后续贪心定型失效。

设边 $a\to b$ 权 $-2$、$b\to c$ 权 $3$、$a\to c$ 权 $4$。加超级源后可得 $h(a)=0,h(b)=-2,h(c)=0$，于是三条新权分别为 $0,1,4$。Dijkstra 在新图求得 $d_a^{\prime }(c)=1$，恢复后仍为 $1-h(a)+h(c)=1$，对应原图路径 $a\to b\to c$。

超级源能到达每个原顶点；若原图含负环，某些端点间可以绕环任意降低路径权，距离不是有限值；算法必须停止，不能继续重赋权。不可达点在各次 Dijkstra 中保持无穷，恢复公式也不能对无穷做普通实数运算。

重赋权只保留路径总权的相对次序，不保留每条边原值。输出若需要路径长度必须恢复，若需要具体路径则保存每次 Dijkstra 的前驱即可，因为最短路径的边序列没有改变。

Johnson 适合边数远小于 $V^2$、存在负边但无负环的全源最短路。稠密图上 Floyd–Warshall 的 $O(V^3)$ 简洁界可能更合适；算法选择应同时考虑图密度和堆实现。

势函数重赋权也出现在最小费用流等算法中。可复用的核心不是“先跑一次 Bellman–Ford”的步骤表，而是端点伸缩不变量与所有残余边非负的证明。