最大流问题（FIFO Push-Relabel 算法）
字数 1788 2025-12-05 13:14:09

最大流问题（FIFO Push-Relabel 算法）

你已经听我介绍过许多最大流算法的变体，但让我再深入一种特别高效的实现——FIFO Push-Relabel 算法。这是一种属于“预流推进”（Push-Relabel）家族的算法，它通过维护一个“预流”而非传统的流，并结合先进先出（FIFO）队列来管理活动顶点，最终计算出网络中的最大流。

题目描述
假设你有一个有向图 G=(V, E)，其中每个顶点 v∈V 都有一个高度标签 h(v)，每条边 (u, v)∈E 都有一个非负的容量 c(u, v)。图中指定了一个源点 s 和一个汇点 t。你的目标是从 s 到 t 推送尽可能多的“流”，使得对于每条边，流量不超过其容量（容量约束），并且对于除了 s 和 t 之外的每个顶点，流入的流量等于流出的流量（流量守恒）。FIFO Push-Relabel 算法高效地解决了这个问题。

解题过程

  1. 核心思想
    Push-Relabel 算法不始终保持流量守恒，而是允许顶点暂时储存多余的流入流量（称为“超额流”）。算法通过两个基本操作逐步调整流量和顶点高度，最终使所有超额流都推送到汇点或回流到源点，从而得到最大流。FIFO 指的是使用一个队列来管理“活动顶点”（即具有超额流的非源非汇顶点），并按照先进先出的顺序处理它们，这有助于平衡性能，避免某些顶点被过度处理。

  2. 初始化
    我们从零流量开始。然后：

    • 设置源点 s 的高度 h(s)=|V|（顶点总数），其他所有顶点的高度 h(v)=0。
    • 对于从源点 s 出发的每条边 (s, v)，我们推送尽可能多的流量，即流量 f(s, v)=c(s, v)。这会在顶点 v 上产生超额流 excess(v)=c(s, v)，而源点 s 可能产生负的超额流（但源汇的超额流不参与后续操作）。
    • 将所有因初始化而产生超额流的非汇点顶点（即 excess(v)>0 且 v≠t）加入一个 FIFO 队列中，它们成为“活动顶点”。

  3. 两个基本操作
    算法循环从队列中取出活动顶点 u，并尝试消除其超额流，主要依靠两个操作：

    • 推送（Push）操作：如果顶点 u 有超额流（excess(u)>0），并且存在一条从 u 出发的边 (u, v)，满足 h(u)=h(v)+1 且该边还有剩余容量（即容量 c(u, v) 减去当前流量 f(u, v) 为正），那么我们可以沿这条边从 u 向 v 推送一部分流。推送的量是 min(excess(u), 剩余容量)。推送后，更新 u 和 v 的超额流，以及边 (u, v) 和反向边 (v, u) 的流量（反向边允许“退回”流）。如果 v 不是源点或汇点，且因这次推送变成了具有超额流的新活动顶点，则将 v 加入队列。
    • 重标记（Relabel）操作：如果顶点 u 有超额流，但不存在满足推送条件的邻接边（即所有从 u 出发的边要么已满，要么指向高度不低于 h(u)-1 的顶点），那么我们增加 u 的高度：h(u)=1+min{ h(v) | (u, v) 有剩余容量 }。这为后续的推送创造了可能。

  4. FIFO 队列管理
    算法使用一个队列来存储活动顶点。每次从队列前端取出一个顶点 u，然后反复对其尝试推送或重标记，直到 excess(u) 变为 0 或者 u 被重标记。在过程中，如果邻接顶点 v 因推送变成新的活动顶点，且不在队列中，则将其加入队列尾部。当 u 的超额流被清空（或无法立即清空但已被重标记）后，如果队列不为空，则处理下一个顶点。这样保证了顶点按照成为活动顶点的顺序被处理，避免饥饿现象。

  5. 终止条件
    当队列为空时，算法终止。此时，所有非源非汇顶点的超额流均为 0，流量守恒得以满足，得到的便是最大流。可以证明，算法最终一定会终止，并且结果正确。

  6. 复杂度
    FIFO Push-Relabel 算法的时间复杂度为 O(V³)，其中 V 是顶点数。虽然这个上界不如某些更高级的 Push-Relabel 变体（如最高标号预流推进算法 O(V²√E)），但 FIFO 版本实现相对简单，在实践中通常表现良好，尤其适合对实现简洁性有要求的场景。

通过上述步骤，FIFO Push-Relabel 算法以一种动态调整高度和局部推送的方式，高效地解决了最大流问题，是图论中经典且实用的算法之一。

最大流问题（FIFO Push-Relabel 算法） 你已经听我介绍过许多最大流算法的变体，但让我再深入一种特别高效的实现——FIFO Push-Relabel 算法。这是一种属于“预流推进”（Push-Relabel）家族的算法，它通过维护一个“预流”而非传统的流，并结合先进先出（FIFO）队列来管理活动顶点，最终计算出网络中的最大流。 题目描述 假设你有一个有向图 G=(V, E)，其中每个顶点 v∈V 都有一个高度标签 h(v)，每条边 (u, v)∈E 都有一个非负的容量 c(u, v)。图中指定了一个源点 s 和一个汇点 t。你的目标是从 s 到 t 推送尽可能多的“流”，使得对于每条边，流量不超过其容量（容量约束），并且对于除了 s 和 t 之外的每个顶点，流入的流量等于流出的流量（流量守恒）。FIFO Push-Relabel 算法高效地解决了这个问题。 解题过程 核心思想 Push-Relabel 算法不始终保持流量守恒，而是允许顶点暂时储存多余的流入流量（称为“超额流”）。算法通过两个基本操作逐步调整流量和顶点高度，最终使所有超额流都推送到汇点或回流到源点，从而得到最大流。FIFO 指的是使用一个队列来管理“活动顶点”（即具有超额流的非源非汇顶点），并按照先进先出的顺序处理它们，这有助于平衡性能，避免某些顶点被过度处理。 初始化 我们从零流量开始。然后： 设置源点 s 的高度 h(s)=|V|（顶点总数），其他所有顶点的高度 h(v)=0。 对于从源点 s 出发的每条边 (s, v)，我们推送尽可能多的流量，即流量 f(s, v)=c(s, v)。这会在顶点 v 上产生超额流 excess(v)=c(s, v)，而源点 s 可能产生负的超额流（但源汇的超额流不参与后续操作）。 将所有因初始化而产生超额流的非汇点顶点（即 excess(v)>0 且 v≠t）加入一个 FIFO 队列中，它们成为“活动顶点”。 两个基本操作 算法循环从队列中取出活动顶点 u，并尝试消除其超额流，主要依靠两个操作： 推送（Push）操作 ：如果顶点 u 有超额流（excess(u)>0），并且存在一条从 u 出发的边 (u, v)，满足 h(u)=h(v)+1 且该边还有剩余容量（即容量 c(u, v) 减去当前流量 f(u, v) 为正），那么我们可以沿这条边从 u 向 v 推送一部分流。推送的量是 min(excess(u), 剩余容量)。推送后，更新 u 和 v 的超额流，以及边 (u, v) 和反向边 (v, u) 的流量（反向边允许“退回”流）。如果 v 不是源点或汇点，且因这次推送变成了具有超额流的新活动顶点，则将 v 加入队列。 重标记（Relabel）操作 ：如果顶点 u 有超额流，但不存在满足推送条件的邻接边（即所有从 u 出发的边要么已满，要么指向高度不低于 h(u)-1 的顶点），那么我们增加 u 的高度：h(u)=1+min{ h(v) | (u, v) 有剩余容量 }。这为后续的推送创造了可能。 FIFO 队列管理 算法使用一个队列来存储活动顶点。每次从队列前端取出一个顶点 u，然后反复对其尝试推送或重标记，直到 excess(u) 变为 0 或者 u 被重标记。在过程中，如果邻接顶点 v 因推送变成新的活动顶点，且不在队列中，则将其加入队列尾部。当 u 的超额流被清空（或无法立即清空但已被重标记）后，如果队列不为空，则处理下一个顶点。这样保证了顶点按照成为活动顶点的顺序被处理，避免饥饿现象。 终止条件 当队列为空时，算法终止。此时，所有非源非汇顶点的超额流均为 0，流量守恒得以满足，得到的便是最大流。可以证明，算法最终一定会终止，并且结果正确。 复杂度 FIFO Push-Relabel 算法的时间复杂度为 O(V³)，其中 V 是顶点数。虽然这个上界不如某些更高级的 Push-Relabel 变体（如最高标号预流推进算法 O(V²√E)），但 FIFO 版本实现相对简单，在实践中通常表现良好，尤其适合对实现简洁性有要求的场景。 通过上述步骤，FIFO Push-Relabel 算法以一种动态调整高度和局部推送的方式，高效地解决了最大流问题，是图论中经典且实用的算法之一。