xxx 最大流问题的 FIFO Push-Relabel 算法

我们先明确一个问题：给定一个有向图，其中每条边有一个容量，以及一个源点s 和一个汇点t，我们希望从 s 到 t 尽可能多地“流”过一些流量，同时每条边上的流量不能超过其容量，且除了 s 和 t 外，每个顶点流入的流量必须等于流出的流量（流量守恒）。如何用计算机高效地计算最大流量？

之前你可能听过 Ford-Fulkerson 方法的增广路思想，或者 Dinic 的分层阻塞流算法。而 Push-Relabel 算法采用了一种不同的思路：它不要求始终保持一个合法的流（即满足流量守恒的流），而是允许“预流”的存在，并不断通过“推送”和“重标记”操作，最终调整成一个合法的最大流。我们今天要讲的是 Push-Relabel 算法的一种具体实现策略：FIFO Push-Relabel 算法。

1. 问题描述

输入：

• 一个有向图 G = (V, E)，顶点数 n = |V|，边数 m = |E|。
• 每条边 e ∈ E 有一个非负的容量 c(e)。
• 一个指定的源点 s ∈ V 和一个汇点 t ∈ V。

输出：

• 一个从 s 到 t 的最大流值 f_max。
• 同时，可以输出每条边上的具体流量分配。

2. 核心思想：从“预流”和“高度”出发

Push-Relabel 算法不再像增广路算法那样，每一步都保持一个合法的流。它维护两个核心变量：

1. 预流 (Preflow)：一个函数 f: E → R，满足：
   • 容量限制：对每条边 (u, v)，有 0 ≤ f(u, v) ≤ c(u, v)。
   • 松弛的守恒性：对所有顶点 u ∈ V \ {s, t}，有 流入量 ≥ 流出量。即，允许顶点“暂时”囤积一些多余的流量（称为超额流）。
   • 源点 s 只有流出，汇点 t 只有流入（算法中汇点的高度特殊处理）。
2. 高度函数 (Height/Label Function) h: V → N (非负整数)：
   • 对源点，初始化 h(s) = n (顶点总数)。
   • 对其它顶点，初始化 h(u) = 0。
   • 算法始终维持一个关键性质：如果存在从 u 到 v 的残量边 (即残量容量 r(u, v) = c(u, v) - f(u, v) > 0)，那么 h(u) ≤ h(v) + 1。这意味着，我们只允许从高的顶点向低的（最多低1个单位）的顶点“推”流量。

算法的最终目标：通过一系列操作，消除所有顶点（除了 s 和 t）的超额流。此时，预流就变成了一个合法的最大流。

3. 两个基本操作

为了达到目标，算法只有两种原子操作：

• 推送 (Push)：

  • 条件：对于顶点 u（有超额流 e(u) > 0），找到它的一个邻居 v，使得残量容量 r(u, v) > 0 且 h(u) = h(v) + 1。
  • 动作：从 u 向 v 推送尽可能多的流量。推送量 Δ = min(e(u), r(u, v))。然后更新 f(u, v) += Δ, f(v, u) -= Δ (这是为了处理反向边)，并更新超额流 e(u) -= Δ, e(v) += Δ。
  • 类型：如果推送后，边 (u, v) 的残量容量 r(u, v) 变为 0，这次推送称为饱和推送，否则称为非饱和推送。一次非饱和推送会清空 u 的超额流。

• 重标记 (Relabel)：

  • 条件：顶点 u 有超额流 (e(u) > 0)，但没有一个邻居 v 满足推送条件 (即对于所有 r(u, v) > 0 的邻居 v，都有 h(u) ≤ h(v))。也就是说，u 自己不够“高”，无法把超额流推给任何邻居。
  • 动作：将 u 的高度增加到其“最低可推送邻居高度+1”。即 h(u) = 1 + min{ h(v) | (u, v) 是残量边 }。这就像是“垫高”u，以便后续能推送出去。

4. FIFO Push-Relabel 算法步骤

“FIFO”是一种调度策略，它用一个先进先出的队列来管理有超额流的活跃顶点（源点s和汇点t除外），决定了我们处理这些顶点的顺序。这是 Push-Relabel 算法家族中最简单直观的实现之一。

初始化：

1. 初始化高度：h(s) = n, h(u) = 0 (对于所有 u ≠ s)。
2. 初始化流和超额流：将所有从 s 出发的边 (s, v) 的流量 f(s, v) 设为其容量 c(s, v)，即“灌满”这些边。相应地，v 的超额流 e(v) = c(s, v)。s 的超额流 e(s) 为负的这些流出总和。其它边流量为0。
3. 初始化一个队列 Q，将所有在初始化后拥有正超额流 e(v) > 0 的顶点 v (v ≠ s, t) 加入队列 Q。

主循环：

while 队列 Q 不为空:
    从队首取出一个顶点 u
    // 在 u 的高度改变之前，尝试将它所有的超额流都推送出去
    while e(u) > 0:
        遍历 u 的所有邻居 v（在残量网络中）:
            if r(u, v) > 0 and h(u) == h(v) + 1:
                执行 Push(u, v) 操作
                if v 不是 s, t 且 推送操作使 v 的超额流从 0 变为正数:
                    将 v 加入队列 Q 的末尾
        // 如果遍历完所有邻居，u 的超额流仍未清空
        if e(u) > 0:
            执行 Relabel(u) 操作
            // 重标记后，u 的高度增加了，但可能仍然无法推送，所以不需要立刻将它重新入队？
            // 这里有一个关键点：在 FIFO 实现中，我们通常会在“本次处理 u 的循环”结束后，
            // 如果 e(u) 仍然 > 0，则将 u 重新放回队列末尾，等待下一次处理。
            // 伪代码的一个更清晰写法是：
            if 在遍历所有邻居的过程中，成功执行了至少一次推送:
                // 什么都不做，继续内部 while 循环尝试推送
            else:
                // 意味着没有可推送的邻居，需要重标记
                Relabel(u)
                // 重标记后，跳出对邻居的遍历，但不清除 u
                break (跳出遍历邻居的循环)
    // 当 e(u) 变为 0 时，或者因为重标记而跳出内部循环时
    if e(u) > 0:
        将 u 重新加入队列 Q 的末尾

结束：当队列为空时，所有顶点 (除了 s 和 t) 的超额流均为 0。此时，汇点 t 接收的总流量就是最大流的值。

5. 逐步详解与例子

考虑一个简单网络：
顶点：s, a, b, t
边（格式：起点， 终点， 容量）:
(s, a, 3)
(s, b, 2)
(a, b, 2)
(a, t, 2)
(b, t, 3)

步骤 0: 初始化

• 高度：h(s)=4, h(a)=h(b)=h(t)=0。
• 从 s 灌流：
  • 边(s, a)：f=3, e(a)=3。
  • 边(s, b)：f=2, e(b)=2。
• 队列 Q: [a, b] (因为 e(a)=3, e(b)=2)。

步骤 1: 处理 a (队首)

• e(a)=3 > 0。检查邻居：
  • 邻居 b: r(a,b)=c(a,b)-f(a,b)=2-0=2>0。h(a)=0, h(b)=0。不满足 h(a) = h(b)+1 (0=0+1? 不成立)。不能推。
  • 邻居 t: r(a,t)=2>0。h(a)=0, h(t)=0。同样不满足条件。不能推。
• 没有可推送的邻居，执行重标记 Relabel(a)：
  • 最小邻居高度 min(h(b), h(t)) = min(0, 0) = 0。
  • 新高度 h(a) = 0 + 1 = 1。
• e(a) 仍为 3 > 0，将 a 重新加入队尾。Q 变为 [b, a]。

步骤 2: 处理 b (队首)

• e(b)=2 > 0。检查邻居：
  • 邻居 t: r(b,t)=3>0。h(b)=0, h(t)=0。不满足条件。不能推。
• 没有可推送邻居，执行重标记 Relabel(b)：
  • 最小邻居高度 h(t)=0。
  • 新高度 h(b) = 0 + 1 = 1。
• e(b) 仍为 2 > 0，将 b 重新加入队尾。Q 变为 [a, b]。

步骤 3: 处理 a (队首)

• e(a)=3, h(a)=1。检查邻居：
  • 邻居 b: r(a,b)=2>0, h(a)=1, h(b)=1。满足 h(a) = h(b) + 1? 1 = 1+1? 不成立！ 仍然不能推。
  • 邻居 t: r(a,t)=2>0, h(a)=1, h(t)=0。满足 h(a) = h(t) + 1! 1 = 0+1 成立。
• 执行推送 Push(a, t):
  • Δ = min(e(a)=3, r(a,t)=2) = 2。
  • f(a, t) 从 0 变为 2。e(a) 从 3 变为 1。e(t) 从 0 变为 2。
  • 这是饱和推送，边(a,t) 满了。
• e(a)=1 仍然 >0。继续检查邻居：
  • 邻居 b: 再次检查，条件仍然不满足 (1 = 1+1? 不成立)。
  • 邻居 t: 残量 r(a,t)=0，不可推。
• 没有可推送邻居，执行重标记 Relabel(a)：
  • 邻居 b 的高度是 1，邻居 t 已满不考虑。
  • 新高度 h(a) = 1 + 1 = 2。
• e(a)=1 > 0，将 a 重新加入队尾。Q 变为 [b, a]。

步骤 4: 处理 b (队首)

• e(b)=2, h(b)=1。检查邻居：
  • 邻居 t: r(b,t)=3>0, h(b)=1, h(t)=0。满足 h(b) = h(t) + 1! 1 = 0+1 成立。
• 执行推送 Push(b, t):
  • Δ = min(e(b)=2, r(b,t)=3) = 2。
  • f(b, t) 从 0 变为 2。e(b) 从 2 变为 0。e(t) 从 2 变为 4。
  • 这是非饱和推送，b 的超额流清空了！
• e(b)=0，所以 b 不需要重新入队。Q 变为 [a]。

步骤 5: 处理 a (队首)

• e(a)=1, h(a)=2。检查邻居：
  • 邻居 b: r(a,b)=2>0, h(a)=2, h(b)=1。满足 h(a) = h(b) + 1! 2 = 1+1 成立。
• 执行推送 Push(a, b):
  • Δ = min(e(a)=1, r(a,b)=2) = 1。
  • f(a, b) 从 0 变为 1。e(a) 从 1 变为 0。e(b) 从 0 变为 1。
  • 非饱和推送，a 的超额流清空。b 获得超额流 1。
• 因为 b 的超额流从 0 变为 1，将 b 加入队尾。Q 变为 [b]。

步骤 6: 处理 b (队首)

• e(b)=1, h(b)=1。检查邻居：
  • 邻居 t: r(b,t)=3-2=1>0, h(b)=1, h(t)=0。满足条件。
• 执行推送 Push(b, t):
  • Δ = min(e(b)=1, r(b,t)=1) = 1。
  • f(b, t) 从 2 变为 3。e(b) 从 1 变为 0。e(t) 从 4 变为 5。
  • 饱和推送，边(b,t)满了，b 的超额流清空。
• e(b)=0，不出队也不入队。Q 变为空。

算法结束。汇点 t 的超额流 e(t) = 5 就是最大流值。最终流分布：s->a:3, s->b:2, a->b:1, a->t:2, b->t:3。

6. 算法正确性与复杂度

• 正确性：Push-Relabel 算法的正确性基于高度函数和两个操作维持的性质。最终没有活跃顶点时，预流即合法流。可以证明此时的流是最大的（基于高度引理和源点高度始终为 n）。
• 时间复杂度：
  • 重标记操作次数为 O(n^2)。
  • 饱和推送次数为 O(nm)。
  • FIFO 实现下的非饱和推送次数为 O(n^3)。这是其复杂度上界。
  • 因此，FIFO Push-Relabel 算法的总时间复杂度为 O(n^3)，其中 n 是顶点数。在实际应用中通常比这个上界快。

总结一下，FIFO Push-Relabel 算法通过维护一个高度场，允许流量“暂时”积压在中间顶点，并像水流从高处向低处流动一样，用队列管理需要处理的“积水点”，最终将所有积水排到汇点，从而高效地找到了最大流。它避免了寻找增广路的过程，在某些类型的图上（尤其是稠密图）有很好的表现。