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).

高度标签 $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$ ，所以上式候选集非空。为证这一点，设从该点残量可达的集合 $U$ 不含 $s$ 。任何从外部进入 $U$ 的原弧都只能承载零流，否则它的反向残量会离开 $U$ 。于是 $U$ 的总超额不大于零；但 $U$ 中各点均非源，超额非负，其中 active 顶点还严格为正，矛盾。这里汇点的非负超额同样参与求和。Push 保持容量、预流与高度有效性；relabel 在所有残量邻点都不比 $u$ 低时严格提高 $h(u)$ ，并重新恢复一条可用下坡边。

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

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

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

在邻接表、正反残量配对索引与精确单位成本算术下，维护 active 顶点容器及每点的当前出弧位置；检查失败后推进位置，只有该点 relabel 后才重新扫描其邻接表。这样每个高度阶段只扫描各出记录一次，避免为每次 push 都从头寻找候选。计入初始化，generic push–relabel 的确定性最坏时间为 $O(n+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，把能到达 $t$ 的非源顶点改标为真实残量距离；源仍固定为 $n$ ，不可达点需采用保持有效性的有限标签，并相应重置扫描状态。gap heuristic 发现某个高度层为空后，可整体抬高无法到汇的一侧。采用这些启发式时，还需规定调用频率，并计入全局搜索与状态重置成本；上面的高度单调操作计数针对基本版本。浮点实现的“正残量”判断可能受舍入影响，组合界按精确算术解释。

推论与应用

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

费用缩放也有局部Push/Relabel，但价格标签和许可条件不同：许可弧的约化费用为负，阶段允许正负超额，Relabel降低价格并排除自环候选。它需要ε约束、许可图无环和可行比较流的价格降幅证明，不能直接沿用最大流的高度标签论证。

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。

形式陈述 ​

反向链接

形式陈述