预流推进算法(Push-Relabel)

预流推进算法(Push-Relabel,又称压入重标记算法)是一类求解网络最大流的经典方法。与 Ford-Fulkerson 系列沿增广路整条推流不同,它允许中间节点暂时积累超额流量(预流),通过局部的推流(Push)和重贴标签(Relabel)两种操作逐步调整,最终把多余流量退回源点,得到最大流。

概述

该算法由高德堡与塔扬提出,其核心创新在于放松了流守恒约束:计算过程中允许节点流入大于流出,形成预流,只在算法结束时恢复守恒。借助节点高度标号引导流量走向,它避免了反复寻找完整增广路,在稠密网络上往往更高效。

核心原理

• 预流与超额:每个节点维护超额流量,即流入减流出的差值;源点先把邻接边全部灌满。
• 高度标号:每个节点有一个高度值,规定只能把流量推向高度恰好低一层的邻接节点。
• 推流操作:当节点有超额且存在可行的下坡边时,沿该边推送尽可能多的流量。
• 重贴标签:当节点有超额却无下坡出边时,抬高自身高度,使其获得新的可推方向。
• 优化版本:采用最高标号选择或先进先出策略可显著改善复杂度,配合间隙优化实际表现优异。

应用场景

预流推进适用于各类最大流与最小割建模,如二分图匹配、项目选择、图像分割中的能量最小化、网络可靠性评估等。在边数远大于点数的稠密图上,它相对增广路算法优势明显,是许多高性能最大流库的底层实现。

常见问题

问:预流推进比 Dinic 算法一定更快吗?答:不一定。二者理论复杂度接近,稠密图上预流推进常更优,而稀疏图或单位容量图上 Dinic 往往表现更好,实际选择需结合数据特征。

问:为什么算法结束时超额会自动清零?答:当没有节点再存在既有超额又能推流的情形时,多余流量会因高度限制被逐步退回源点,最终除源汇外所有节点恢复流守恒。