算法与数据结构 · 第 23 课

Johnson 重赋权:怎样把负权边变成非负,又完全不改变最短路径?

2026 年 11 月 11 日|第 4 周 · 第 3 天|讲授约 17 分钟,自测另计

第 21 课 Bellman–Ford 能处理负边,却需要多轮松弛;第 22 课 Dijkstra 很快,却要求边权非负。今天把二者组合:先运行一次 Bellman–Ford 找到每个顶点的“势函数”,再修改边权,让全部边非负;之后对每个源点运行 Dijkstra。 最难的地方不是公式,而是证明改了边权以后,原来的最短路径为什么还最短。

一、学习目标与问题边界(约 1 分钟)

本节要掌握四件事:① 为什么直接给每条边“加同一个数”不行;② 势函数 h 的来源与非负性证明;③ 重赋权后任意两点之间的最短路径如何保序、怎样还原距离;④ Johnson 的全点对最短路(APSP)步骤、复杂度和负环边界。

模型:有向图 G=(V,E),n= V ,m= E ,边权允许负数。假设没有负权环;若存在负环,算法必须先检测并报告。允许不连通,无法到达的点对距离记为 +∞。路径可包含边权为负的边,但在无负环时最短路线总可选为简单路径。

二、为什么不能给所有边统一加 10?(约 2 分钟)

设 A 到 D 有两条路线:一条只有一条边,代价 5;另一条经过三条边,每条代价 1,总代价 3。原本三条边的路线更短。若所有边统一 +10,前者变成 15,后者变成 33,最短路线反而换了。

问题在于不同路径使用的边数不同。要让路径之间的优劣次序不变,我们需要一种变换:对于固定起点 s 和终点 t,任何 s→t 路径都只增加同一个常数,不依赖路径到底经过哪些中间顶点。

定义每个顶点的势函数 h(v),以及新边权:

[ \boxed{w’(u,v)=w(u,v)+h(u)-h(v).} ]

你可以把 h 想成每个顶点的“参考高度”:沿 u→v 走时,原边权加上起点势能、减去终点势能。现在问题变成:如何找到 h,让所有 w’≥0?

三、势函数从哪里来:加一个超级源点 q(约 3 分钟)

先在原图外新增顶点 q,并向每个原顶点 v 添加一条 q→v、权重为 0 的边。然后运行一次 Bellman–Ford:

[ \boxed{h(v)=\delta(q,v).} ]

因为 q 可直接到达每个点,若没有负环,所有 h(v) 都是有限的;它们可能是 0 或负数,不要求非负。这个做法也保证即使原图有互不可达的不同分量,任何分量中的负环都会从 q 可达并被检测。

为什么这些 h 能消除负边?考虑任意原边 u→v:先从 q 到 u 走最短路,再走此边,就是一条到 v 的候选路线。所以最短路一定满足

[ h(v)\le h(u)+w(u,v). ]

把它移项:

[ \boxed{w(u,v)+h(u)-h(v)\ge0.} ]

这正好就是 w’(u,v)≥0。Johnson 的非负性不是凭空假设,而是 Bellman–Ford 最短距离的三角不等式。

flowchart LR
    Q((q)) -->|"0"| A((A))
    Q -->|"0"| B((B))
    Q -->|"0"| C((C))
    Q -->|"0"| D((D))
    A -->|"3"| B
    B -->|"-4"| C
    C -->|"2"| D
    D -->|"4"| B

图中仅画出关键边。q 的零权边是计算势函数的辅助边,不是之后进行原图所有点对查询时要保留的可行路径。

四、最重要的证明:路径上的势函数会相互抵消(约 3 分钟)

设任意路径为

[ P:s=v_0\to v_1\to\cdots\to v_k=t. ]

新路径总权重为

[ \begin{aligned} w’(P) &=\sum_{i=0}^{k-1}\big[w(v_i,v_{i+1})+h(v_i)-h(v_{i+1})\big]
&=w(P)+\underbrace{h(v_0)-h(v_1)+h(v_1)-\cdots-h(v_k)}_{\text{中间势函数抵消}}
&=\boxed{w(P)+h(s)-h(t)}. \end{aligned} ]

这叫望远镜求和(telescoping sum)。因为同起终点的每条路径都加上相同的 h(s)−h(t),所以它们的大小比较、最小值对应的路径完全不变,只不过数值长度可能变化。

因此运行 Dijkstra 得到新权距离 d’(s,t) 后,原图距离必须还原为

[ \boxed{\delta(s,t)=d’(s,t)-h(s)+h(t).} ]

不要把加减号弄反:先由 w’(P)=w(P)+h(s)−h(t),再把 w(P) 单独移到左边。重赋权不要求距离数值保持不变,只要求最短路径次序不变。

五、完整数值 Trace:负边变成 0,Dijkstra 仍然正确(约 3 分钟)

考虑四点图,除图中关键边外还有 A→C(8)、A→D(10)、B→D(5):

flowchart LR
    A((A)) -->|"3"| B((B))
    A -->|"8"| C((C))
    A -->|"10"| D((D))
    B -->|"-4"| C
    B -->|"5"| D
    C -->|"2"| D
    D -->|"4"| B

从 q 出发,先有 q→A/B/C/D 的 0 权边。同步 Bellman–Ford 逐轮更新的关键值如下(列中不含 q):

完成轮次 h(A) h(B) h(C) h(D) 新信息
1 0 0 0 0 q 直达全部顶点
2 0 0 −4 0 B→C 使 C 下降
3 0 0 −4 −2 C→D 使 D 下降
4 0 0 −4 −2 稳定,没有负环

现在每条原边用 w’=w+h(u)−h(v) 替换:

原边 原权重 w 新权重 w’
A→B 3 3
A→C 8 12
A→D 10 12
B→C −4 0
B→D 5 7
C→D 2 0
D→B 4 2

所有新边权都非负!从 A 运行 Dijkstra:A(0) 首先给 B=3、C=12、D=12;B(3) 将 C 改为 3、D 改为 10;C(3) 再将 D 改为 3。所以新权下 d’(A,D)=3,最短路线是 A→B→C→D。

还原原图距离:

[ \delta(A,D)=3-h(A)+h(D)=3-0-2=1. ]

直接验算旧边权:3+(−4)+2=1,确实相同。注意原图最短距离可以是负数,只是重赋权图的边和距离都非负。

六、Johnson 的整体伪代码与正确性(约 2 分钟)

JOHNSON(G):
    建新源 q;对每个 v∈V 添加 (q,v,0)
    h = BELLMAN_FORD(G + q, q)
    if 检测到负环: return NEGATIVE_CYCLE

    对每条原边 (u,v,w):
        wprime(u,v) = w + h[u] - h[v]   # 必非负

    for each s in V:
        dprime = DIJKSTRA(V, E, wprime, s)
        for each t in V:
            if dprime[t] == +INF:
                answer[s][t] = +INF
            else:
                answer[s][t] = dprime[t] - h[s] + h[t]
    return answer

正确性拆成三步: Bellman–Ford 无负环时产生满足每条边差分约束的 h;因此新权非负,Dijkstra 的“最小距离安全定型”证明适用;最后望远镜求和表明重赋权保持同一对端点所有路径的排序,恢复公式就给出原图最短距离。若 s 无法到 t,边权变化不可能创造新路径,仍返回 +∞。

一个容易忽略的边界:不能直接把未还原的 d’(s,t) 当作最终答案,也不能在 Dijkstra 过程中保留 q 的零权辅助边,否则会求解错误的图。

七、复杂度、失败条件与选择算法(约 2 分钟)

辅助图有 n+1 个顶点、m+n 条边。Bellman–Ford 最坏 O(n(m+n)) 时间。重赋权遍历 m 条边需 O(m)。在原图上从 n 个源点分别运行二叉堆 Dijkstra:使用 decrease-key 的实现每次可记为 O((n+m)log n),全部为 O(n(n+m)log n);若用上一课允许重复入堆的 lazy heap,可以用更精确的 O(n[n+m+(m+1)log(m+2)]) 表述。工作内存通常是 O(n+m),若显式保存全部 n×n 距离答案,还需要 Θ(n²) 输出空间。

三种算法的角色很清楚:Bellman–Ford 是含负边的单源基线,还能检测可达负环;Dijkstra 是非负权单源方法;Johnson 是无负环、可能含负边的全点对最短路。稀疏图上通常比从每个源点都运行 Bellman–Ford 更划算;若图很稠密,Floyd–Warshall 的 O(n³) 也值得比较。具体优劣取决于 m、图表示与堆实现。

反例与边界: ①存在负环时,绕环反复行走可使某些点对代价趋向 −∞,不能输出普通有限最短路矩阵;②仅用某个原顶点启动 Bellman–Ford,可能漏检其他分量中的负环,所以要加 q;③随便指定 h 不一定满足非负性,不能仅凭望远镜恒等式就使用 Dijkstra;④零权新边完全合法,Dijkstra 要求的是非负而非严格正。

八、今日总结与下一课(约 1 分钟)

请把 Johnson 理解成三个因果关系,而不是背一条公式:

[ \boxed{ \text{Bellman–Ford 给出 }h(v)\le h(u)+w(u,v) \Longrightarrow w’(u,v)\ge0 } ]

[ \boxed{ \text{路径势函数望远镜抵消} \Longrightarrow \text{同端点最短路线保持不变} } ]

[ \boxed{ \text{Dijkstra 求新距离} \Longrightarrow \delta(s,t)=d’(s,t)-h(s)+h(t) } ]

下一课(2026-11-12,第 24 课):最小生成树(MST)与割性质。 从 Kruskal、Prim 的共同正确性依据出发,证明为什么跨越一个割的最轻边是“安全”的,并辨析负权、等权与非连通图。

九、四级自测(100 分;首次不公布答案)

前三题客观判分,最后一题开放推导。讲义仅有中立提示;标准答案、解析及评分细则只存放在独立测验 JSON 中。

Lv1|势函数与路径保序的机制|15 分|预计 2 分钟|单选

关于 Johnson 重赋权,哪一项严格正确?

A. 若每条边都满足 h(v)≤h(u)+w(u,v),则新边权非负;对固定起点和终点的所有路径,重赋权只增加同一个常数。

B. 要得到满足要求的势函数,原图中每条边本来就必须非负。

C. 只要图没有负环,把所有 h(v) 都设为 0 就一定得到非负新边权。

D. Johnson 要求每条路径重赋权前后的数值长度完全相等,而不只是最短路径的优劣次序不变。

中立提示:分别检查边的差分约束,以及同一起终点的路径在累加新边权后发生什么。

Lv2|Bellman–Ford 势函数和 Dijkstra 数值 Trace|20 分|预计 4 分钟|单选

有向图顶点为 A、B、C、D,边为 A→B(4)、A→C(6)、B→C(−3)、B→D(7)、C→D(2)。增设超级源点 q,并向四个点各加一条 0 权边。Bellman–Ford 算得势函数 h 后,用 w’(u,v)=w(u,v)+h(u)−h(v) 重赋权,再从 A 运行 Dijkstra。下列哪个四元组 (h(C),h(D),d’(A,D),原图 δ(A,D)) 正确?

A. (−3,−1,4,3)

B. (−3,−1,3,4)

C. (−3,0,4,3)

D. (0,−1,4,3)

中立提示:先利用 q 的 0 权边初始化可行上界,再检查 B→C、C→D 的改进。最后把重赋权距离按起终点势函数差恢复。

Lv3|负环、可行势与纠偏边界|25 分|预计 4 分钟|多选

设原图可能含负边,Johnson 算法要计算所有点对最短路。以下哪些说法成立?(多选)

A. 向原图所有顶点加入来自 q 的 0 权边后,原图任一分量里的负环都从 q 可达,因此 Bellman–Ford 能检测到它。

B. 只要原图不存在负环,任意指定的 h 都保证所有重赋权边非负。

C. 对同一对端点 s、t,即使任意给定的 h 没让边权都非负,恒等式 w’(P)=w(P)+h(s)−h(t) 仍对每一条 s→t 路径成立。

D. 对无负环图,重赋权后 Dijkstra 输出的 d’(s,t) 总可以直接当作原图距离,无需使用 h 还原。

中立提示:把纯代数的望远镜求和,与使用 Dijkstra 所需的非负权条件分开判断;再检查 q 的可达范围。

Lv4|Johnson 全点对最短路算法设计与证明|40 分|预计 10 分钟|开放推导

给定 n≥2 个顶点、m 条有向加权边的图,权重可负,图可能不连通。设计 Johnson 全点对最短路算法。(a)(10分)给出添加超级源点 q、运行 Bellman–Ford、检测任何负环以及构造 h 的步骤;(b)(12分)由 Bellman–Ford 的最短距离不等式严格证明所有 w’(u,v)=w(u,v)+h(u)−h(v)≥0,并证明任意 s→t 路径的权重变化只取决于端点;(c)(10分)说明为何可在新图上从每个 s 运行 Dijkstra,以及如何恢复原距离、处理不可达点,写出关键伪代码;(d)(8分)分析 Bellman–Ford、n 次 Dijkstra、结果矩阵的时间与空间,解释若图有负环为什么不能照常输出有限的所有点对最短路。

中立提示:先证明 h(v)≤h(u)+w(u,v);再将整条路径每条边的新权相加,观察中间顶点势函数的消去。复杂度应区分辅助图、单源堆实现和 n×n 输出。

十、提交与反馈

请回复 Lv1:选项;Lv2:选项及势函数/距离计算;Lv3:全部正确选项;Lv4:(a)–(d) 证明。我会按 15/20/25/40 分逐题评分:80–100 分按原进度推进;60–79 分补势函数或路径保序的针对练习;低于 60 分先复习 Bellman–Ford 最短距离不等式和望远镜求和。补练不修改自然日课号。