HLPP · 最高标号 · 预流推进

HLPP：最高标号预流推进

Dinic 那页 §5 已经把预流推进的骨架跑通：给每个点维护高度与超额，反复对活跃点做 push 或 relabel，没有活跃点时预流自动成为最大流。那份实现选点用的是最高标号规则，但高度的初值全取 0，判死的时机也完全交给 relabel 自己爬。HLPP（highest-label preflow push）在同一骨架上补两处加速，两处都不改变正确性，只改变到达终态所需的操作数。

1 · 朴素预流推进的浪费

朴素版本把所有非源点的高度初始化为 0。这意味着算法对「哪些点离汇点近」一无所知，得靠 relabel 一次抬一格地把地形试出来。

浪费集中在两类点上。第一类是本来就离汇点很远的点：它的高度需要被抬到接近真实距离才能开始有效下推，抬升过程中每一格都要选点、扫边、比较一遍。第二类更糟：超额落在了根本通不到汇点的点上。这些超额注定要退回源点，而退回源点的唯一途径是把高度抬到 $n + 1$ 以上（源点高度为 $n$ ，反向边可行需要 $h[u] = h[s] + 1$ ）。朴素版本只能一格一格抬，每一格都是一次完整的 relabel。

这两类浪费自 Goldberg 与 Tarjan 提出 push-relabel 时便为人所知 [1]，此后的实现研究基本围绕如何压掉它们展开。

2 · 初始高度的来源

第一处加速把初始高度换成精确值。

定义 5.1（global relabeling） 在残量网络上从汇点做一次反向 BFS，令 $h[v]$ 等于 $v$ 到 $t$ 的最短距离；到不了汇点的点留在 $0 $，源点仍置 $h[s] = n$ 。

这份初值直接满足高度函数的合法性要求（每条残量边上 $h[u] \le h[v] + 1$ ），代价是一次 BFS。对第一类点来说，它把「一格格试出来」变成「一次算准」。

高度函数的合法性有一处必须点明的例外：源点。 $h[s] = n$ 是人为抬起的势能，它一开始就违反 $h[s] \le h[v] + 1$ ，而正因为违反，preflow 阶段才能把源边一次灌满、制造出可供推进的超额。写本页配套的测试时先没排除源点，断言 h[u] ≤ h[v] + 1 立刻在初始帧上炸了，classic 网的 $h[s] = 4$ 对着 $h[a] + 1 = 2$ 。断言里排掉 $u = s$ 之后才对。

对第二类点，global relabeling 帮不上忙：通不到汇点的点在反向 BFS 里根本不会被访问，高度留在 0，之后仍要一格格抬。这一类交给第二处加速。

3 · gap 与整批判死

定理 5.2（gap 判据） 设 $cnt[k]$ 为高度等于 $k$ 的非源点个数。若某时刻存在 $k < n$ 使 $cnt[k] = 0$ ，则所有满足 $k < h[v] < n$ 的点 $v$ 都无法在残量网络中到达汇点。

证明设 $v$ 满足 $k < h[v] < n$ 且存在残量路 $v \to t$ 。沿该路每条残量边套用合法性 $h[u] \le h[w] + 1$ ，得标号从 $h[v]$ 到 $h[t] = 0$ 每步至多降 1，故 $\{0, \dots, h[v]\}$ 中每个值都被路上某点取到，其中包括 $k$ 。这与 $cnt[k] = 0$ 矛盾。∎

既然这些点到不了汇点，它们手上的超额只有一个去处：退回源点。算法直接把它们的高度设为 $n + 1$ ，省掉逐格爬升的全过程。这项技巧一般称作 gap 启发式，最早作为 Goldberg 算法的实现改良被单独考察 [3]。这个批量赋值不破坏高度合法性——被判死的集合对残量边是闭合的：若 $v$ 被判死而它的残量邻居 $w$ 未被判死，则 $h[w] \ge h[v] - 1 > k - 1$ ，即 $h[w] \ge k$ ；而 $k$ 层是空的，所以 $h[w] > k$ ， $w$ 同样落在判死区间里（或已经 $\ge n$ ，此时 $h[v] = n+1 \le h[w] + 1$ 仍成立）。

图 3-1 · 搁浅网上的 HLPP，两处加速可独立开关。节点上方

h

为高度、下方

e

为超额，灰色虚线圈为已被 gap 判死的点；下方计数桶给出每个高度层的点数。两个开关都关即退化为 Dinic 那页 §5 的朴素版本，可对照步数与 relabel 次数。

4 · 两个优化的协同

两处加速针对的是不同的浪费，收益本该各自独立、叠加时略有重叠。搁浅网上的实测不是这样。

图 4-1 · 五张网上四种开关组合的步数。末列比较「两个优化各自单独省下的步数之和」与「同时开省下的步数」；单击任一行可高亮。

搁浅网的四个数是 40（都关）、30（只开 global relabeling）、24（只开 gap）、11（都开）。各自单独省下 10 步与 16 步，合计 26；同时开省下 29 步，比各自之和还多 3 步。另外四张网上都没有这个现象，同时开的收益都不超过各自之和。

原因在于两个优化互为前提。gap 要触发，需要某个高度层先被抬空，也就需要点的高度已经分散到若干个中间层上；而在这张网里，中间层是 global relabeling 给出的初始梯度加上 $a \to t$ 饱和后 $a$ 被迫抬升共同造出来的。只开 gap 时初始高度全是 0，中间层要靠 relabel 慢慢堆，堆出来时该省的已经省不回来，那一列停在 24 步，gap 触发了两次却各只判死 2 个点。都开时 gap 只触发一次，一次判死 4 个点。

反过来看第 1 节那两类浪费：global relabeling 治第一类，gap 治第二类，而搁浅网被构造成两类同时严重。这也解释了为什么其他四张网上看不到超线性：它们缺少通不到汇点的支路，第二类浪费本就轻微。

5 · 未实现的周期性重标号

标准 HLPP 实现通常还有第三处加速：每做 $O(V)$ 次 relabel 就重跑一遍反向 BFS，把所有高度重新校准（周期性 global relabeling）。文献里它对大规模网络的实测收益相当可观 [4]。

本页的引擎没有实现它，理由有两条。其一，本系列的网都在 6 个点上下，一次校准的成本高于它能省下的 relabel。其二更要紧：周期性重标号会在某一步把大量点的高度同时改掉，而这一步在单步播放里无法归因到任何一个局部操作上——前一帧到后一帧之间，读者看到的是十几个数字集体跳变。单步动画的价值在于每一帧的变化都能指着一条边或一个点说清缘由，这项优化与之冲突。

复杂度上，最高标号选点规则让 push-relabel 达到 $O(V^2\sqrt{E})$ [2]，优于 Dinic 的 $O(V^2E)$ ，也优于 FIFO 选点的 $O(V^3)$ 。两处加速都不改变这个上界。实务中 push-relabel 系在稠密图上通常快过 Dinic，稀疏图上则常常相反；Cherkassky 与 Goldberg 的实测研究 [4] 给出的结论是：不带 global relabeling 的实现在某些图族上会退化得很厉害，这项优化在工程实现里近乎必备。

至此求最大流的几种算法走完。接下来的最大流最小割定理转向对偶的一面：这五种算法末态那张残量网络里，藏着一个与最大流值相等的最小割。

6 · 参考文献

Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum-flow problem. Journal of the ACM, 35(4), 921–940.
Cheriyan, J., & Maheshwari, S. N. (1989). Analysis of preflow push algorithms for maximum network flow. SIAM Journal on Computing, 18(6), 1057–1086.
Derigs, U., & Meier, W. (1989). Implementing Goldberg's max-flow algorithm: A computational investigation. Zeitschrift für Operations Research, 33(6), 383–403.
Cherkassky, B. V., & Goldberg, A. V. (1997). On implementing the push-relabel method for the maximum flow problem. Algorithmica, 19(4), 390–410.