CSCI3160 Special 11：Johnson 重赋权与传递闭包
原件：Sp11 题目（本地课件） p.1，箭头与权重已视觉核对。 每题先题解后解析；以下是自行题解，不是官方答案。
Problem 1：全部重赋权结果
题解
超级源点到所有原点加零边后，势函数h按a,b,c,d,e,f顺序为0、0、−1、0、−3、−7。新权重如下：
| 有向边 | 原权重w | h(u)−h(v) | 新权重 |
|---|---|---|---|
| a→c | 6 | 1 | 7 |
| a→e | 3 | 3 | 6 |
| b→d | 4 | 0 | 4 |
| c→b | 2 | −1 | 1 |
| c→d | 7 | −1 | 6 |
| c→f | −6 | 6 | 0 |
| d→e | −3 | 3 | 0 |
| e→c | 2 | −2 | 0 |
| f→d | 10 | −7 | 3 |
具体解析
原图横向底边是f→d，不能读成d→f；e→c的箭头指向c。从超级源点所有点初始候选0。边d→e给e=−3，接e→c得到c=−1，再接c→f得到f=−7；这三条负向改善足以给最优势。a、b、d仍为0，因为其他到它们的候选不更小，例如c→b给1，f→d给3。
逐边代入 。例如c→f为−6−1−(−7)=0；f→d为10−7−0=3。所有新边非负也是自检；若读反箭头或写反势差，通常会出现负的新权重。
完整性核验：表中每条边均满足h(v)≤h(u)+w(u,v)，且每个负h值都由上述源路径达到，因此它们确为最短距离，不只是“迭代似乎稳定”的数。
再用一条完整路径检查势差的符号。 原图路径 a→e→c→f 长度为 ；重赋权后是 。差值 正是 。所以把新距离换回原距离必须是 。本图到 f 只能由 c 进入，按表中非负新权重可核对 a→e→c→f 已达最短新距离 6，故这里也核对了一对真正最短距离。
自测：若新最短距离为无穷，应照样做减势加势吗？
含义上仍是不可达，重赋权没有加删原图的边。实现时直接保留不可达标记，不对整数无穷哨兵做普通算术，以免溢出成假距离。
Problem 2：所有边加同一常数不保持最短路径
题解
自取边s→t=1、s→a=−2、a→t=2。最小边权z=−2，原图经a路线长0，优于直达1；统一加2后直达3，经a路线0+4=4，最短路线反转。
具体解析
加常数c会让一条含k条边的路径增加kc。不同路线的边数不同，增加量不一致，足以改变相对大小。这个反例是DAG，不受负环干扰，新权重都非负，却没有保住原问题的解。
Johnson增加的是首尾势差：路径中间顶点抵消，因此同起终点的所有路径增加同一个数。这才是它与统一常数平移的本质区别。
Problem 3：任意势函数都保持负环
题解
对环v₀→v₁→…→vₖ=v₀，求新边权之和，势差逐项抵消：
每个环总权重完全不变，所以负环存在当且仅当重赋权后仍存在。
具体解析
结论对任意h成立，不要求h来自最短路；但任意h不保证所有边非负。只有选Johnson的最短距离势，才额外满足那条最短路不等式。
自取三环边权−3、1、1，总和−1；选顶点势2、−1、4，新边为0、−4、3，总和仍−1。某些边可能变正、某些更负，环整体的符号却不变。因此不能靠势函数“消灭”一个真实负环。
Problem 4：传递闭包
题解
对每个顶点i独立做一次DFS或BFS，令M[i,j]=1当且仅当本次访问到j，其他为0。每次搜索O(n+m)，n次共O(n(n+m))；输出矩阵O(n²)空间。
具体解析
每次换源点都重置访问标记；不能沿用上一个源点已访问的集合，否则把“别人能到达”误当成“当前能到达”。课程允许长度零路径，因此M[i,i]=1。若采用仅正长度可达的不同定义，对角线需另行判断环，不能混用。
自取a→b、b→c：按a,b,c排列，矩阵为三行[1,1,1]、[0,1,1]、[0,0,1]。搜索算法正好枚举所有可达点，既不会凭顶点编号添边，也不会遗漏经过多条边的间接可达。
来源与证据
Sp11 p.1。原图9条有向边、势函数与重赋权表已独立计算核验；反例与闭包小图为本文自取。