Push–relabel 最大流算法

形式陈述 ​

输入是容量 $c(e)\ge 0$ 的有限有向网络、源 $s$ 与汇 $t$；输出最大流公理库最大流Maximum flow在容量与流守恒约束下最大化源到汇净流量的问题。。中间状态是 preflow：容量约束仍成立，但内部顶点只要求流入不少于流出。令超额

$$e(v)=\sum _{u}f(u,v)-\sum _{w}f(v,w)\ge 0$$

对 $v\ne s,t$ 成立。高度标签满足 $h(s)=|V|,h(t)=0$，且每条正残量边 $(u,v)$ 都有 $h(u)\le h(v)+1$。

初始化时令其他高度为零并饱和源出边。超额为正的内部顶点称 active。若残量边 $(u,v)$ 满足 $h(u)=h(v)+1$，执行 push，流量

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

若 $u$ 没有 admissible edge，则 relabel 为 $1+min\{h(v):c_f(u,v)>0\}$。Push 保持容量与 preflow，relabel 保持高度有效并严格提高 $h(u)$。当没有 active vertex 时流守恒恢复；有效高度不允许残量 $s$–$t$ 路径，否则长度至多 $|V|-1$ 的路径会与 $h(s)=|V|,h(t)=0$ 矛盾。由最大流最小割定理公理库最大流最小割定理Max-flow min-cut theorem网络最大流值等于源汇最小割容量。，所得流最大。一般实现有 $O(V^{2}E)$ 时间上界。

直觉 ​

算法不寻找完整增广路，而把源先压出的流量局部搬运。高度不是物理距离，而是一张证明残量边只能向相近高度移动的标签；有下坡就推，堵住就抬高。多余流最终到达汇，或沿残量反向边退回源。

局部性让算法适合密集网络和并行化，但正确性依赖 preflow、残量容量与高度三个不变量共同维持，不能只把它描述成“模拟水流”。

例子与边界 ​

网络只有 $s\to a$ 容量 $5$、$a\to t$ 容量 $2$ 时，初始化把 $5$ 推到 $a$，其超额为 $5$，这显然还不是可行流。$a$ 重标号后向 $t$ 推 $2$，剩余超额 $3$；继续升高后通过残量反向边把 $3$ 退回 $s$，最终流值为 $2$。

这个例子说明 push 受超额和残量容量共同限制，也说明中间顶点不守恒是设计的一部分。若把 preflow 误当普通流，就会错误断言初始化非法；若忘记反向残量边，无法把过量流退回。

高度不必等于到汇的真实最短距离，global relabel 才会周期性用反向 BFS 更新更精确标签；gap heuristic 也只是加速，不参与基本正确性。浮点容量会涉及终止与数值比较，本页的组合复杂度按精确算术模型理解。

推论与应用 ​

Push–relabel 与增广路算法从不同方向维护最大流证书：前者保证没有 active vertex 后无残量源汇路，后者逐条消除可用增广路。工程实现常用 highest-label、FIFO active queue、global relabel 与 gap heuristic 改善性能。

算法输出还可从最终残量图中取源可达集合构造最小割。这个证书应在终止状态读取；中间 preflow 即使已有相同数值，也未必满足流守恒。

参考资料

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