Push-relabel 指一种用于求解最大流（max flow）问题的经典算法（也称 preflow-push 算法）。它通过在网络中“推送（push）”多余流量，并在需要时“重标号（relabel）”顶点高度（height/label）来逐步逼近最大流。（该词也常用于指这类算法家族。）
/ˈpʊʃ rɪˈleɪbəl/
The push-relabel algorithm is often fast in practice for large graphs.
推送-重标号算法在处理大型图时通常在实践中很快。
In our implementation, push-relabel maintains a preflow and repeatedly applies push and relabel operations until no vertex has excess flow.
在我们的实现中，push-relabel 维护一个预流（preflow），并反复执行推送与重标号操作，直到没有顶点仍有多余流量为止。
该术语由两个常见动词组合而来：push（推送）表示把“多余的流量”沿可行的剩余边送出；relabel（重标号）表示当无法继续推送时，提高顶点的“高度/标签”，以改变可推送的方向与条件。该算法体系与 Goldberg 和 Tarjan 在 20 世纪 80 年代提出的最大流研究密切相关，因此在算法教材与论文中广泛沿用此名称。
Select Language