Push–relabel 最大流算法

形式陈述

输入是有限容量网络，输出最大流。算法的中间状态是预流（preflow）：容量约束仍成立，但内部顶点只要求流入不少于流出。定义超额

e(v)= \sum_{a:\operatorname{head}(a)=v}f(a) -\sum_{a:\operatorname{tail}(a)=v}f(a)\ge0 \qquad(v\ne s,t).

高度标签 $h:V\to\mathbb Z_{\ge0}$ 满足 $h(s)=n=|V|$ 、 $h(t)=0$ ，并对每条正残量记录 $u\to v$ 保持有效性

h(u)\le h(v)+1.

初始化令其他顶点高度为零，并饱和源的所有出弧。超额为正的内部顶点称为 active。若正残量记录 $u\to v$ 满足 $h(u)=h(v)+1$ ，它是 admissible edge，可执行

\Delta=\min\{e(u),c_f(u,v)\}

的 push；正向记录增加原弧流量，反向记录减少原弧流量。若 active 顶点 $u$ 没有 admissible edge，则执行

h(u)\leftarrow 1+\min\{h(v):c_f(u,v)>0\}.

有超额的顶点总能沿既有流的反向残量记录最终回到 $s$ ，所以上式候选集非空。Push 保持容量、预流与高度有效性；relabel 在所有残量邻点都不比 $u$ 低时严格提高 $h(u)$ ，并重新恢复一条可用下坡边。

没有 active vertex 时，中间点流守恒恢复，预流成为可行流。此时不存在残量 $s$ – $t$ 路：若有长度至多 $n-1$ 的简单路，沿高度有效性逐边相加会得到

n=h(s)\le h(t)+(n-1)=n-1,

矛盾。由最大流最小割定理，终态流最大。

在邻接表、正反残量配对索引与精确单位成本算术下，generic push–relabel 的确定性最坏时间为 $O(n^2m)$ 、空间为 $O(n+m)$ 。证明计数的骨架是：有效高度单调增加，active 顶点高度至多 $2n-1$ ；同一弧方向的 saturating push 之间必须发生足够的高度增长，所以这类 push 共 $O(nm)$ 次；以 active 顶点高度和为势，可把 nonsaturating push 总数界为 $O(n^2m)$ 。该界不依赖容量可积性。

直觉

算法先把源能推出的流全部推出，再局部搬运积压。高度不是物理海拔，也不必等于到汇的真实距离；它是一份证明标签，保证流只沿恰好下降一层的残量记录推送。某处没有下坡，就提高该点，直到它能把超额送向汇或沿反向记录退回源。

这种局部放电无需先找到完整源汇路。代价是中间状态不再满足普通流守恒，正确性必须同时追踪容量、预流非负超额和高度有效性，不能只凭水流比喻判断操作是否合法。

Push–relabel 最大流算法：高度—超额状态转移图 — Push–relabel 最大流算法示意图

例子与边界

网络只有 $s\to a$ 容量 $5$ 、 $a\to t$ 容量 $2$ ，且 $n=3$ 。初始化令 $h(s)=3$ 并把 $5$ 全推到 $a$ ，所以 $e(a)=5$ 。第一次 relabel 把 $h(a)$ 设为 $1$ ，随后向 $t$ 推 $2$ ；剩余 $e(a)=3$ 。此时唯一有余量的出方向是反向记录 $a\to s$ ，其目标高度为 $3$ ，于是再次 relabel 得 $h(a)=4$ ，再把 $3$ 退回源。终态流值为 $2$ ，中间点恢复守恒。

若把初始化预流误当普通流，会错误拒绝这个合法中间状态；若遗漏反向残量记录，过量的 $3$ 无处退回。平行与反平行原弧同样要靠记录 ID 和反向索引区分，不能只以端点查找待更新弧。

global relabel 可从 $t$ 在反向残量图上做 BFS，周期性把标签更新为更精确的距离下界；gap heuristic 发现某个高度层为空后，可整体抬高无法到汇的一侧。它们保持基本不变量并改善实践性能，但不属于算法定义。浮点实现的“正残量”判断可能受舍入影响，组合界按精确算术解释。

推论与应用

Ford–Fulkerson 方法始终维护可行流并沿完整增广路提高流值；Push–Relabel 维护预流并通过局部 push/relabel 消除 active vertex。前者在任意实容量、任意选路下可能不终止，后者的组合操作界与流值、容量分母无关。

active vertex 的选择规则形成多种实现：FIFO 用普通队列，highest-label 优先放电最高顶点，relabel-to-front 按一次扫描次序调整。它们共享基本正确性，但具体复杂度与工程表现需按策略分别说明。

终止后可在最终残量图中取源可达集构造最小割。中间预流即使源净流出数值已经等于最优值，也可能仍在内部积压超额，不能提前作为可行最大流输出。

参考资料

Andrew V. Goldberg and Robert E. Tarjan, “A New Approach to the Maximum-Flow Problem,” Journal of the ACM 35(4), 1988, pp. 921–940。
Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin, Network Flows, Prentice Hall, 1993，Ch. 7。

形式陈述 ​

反向链接

形式陈述