最大流问题的 FIFO 顶点高度重标算法（FIFO Push-Relabel with Global Relabeling 优化）
字数 2482 2025-12-09 16:42:45

最大流问题的 FIFO 顶点高度重标算法（FIFO Push-Relabel with Global Relabeling 优化）

题目描述：
给定一个有向图，每条边有一个非负容量。指定一个源点 \(s\) 和一个汇点 \(t\)，求解从 \(s\) 到 \(t\) 的最大流量。我们使用基于顶点高度重标（Push-Relabel）框架的算法，并引入两种关键优化：先进先出（FIFO） 的顶点选择顺序，以及周期性的全局重标（Global Relabeling）。请讲解这个算法的原理、步骤和复杂度。

解题过程循序渐进讲解：

1. 回顾 Push-Relabel 算法的基本思想

Push-Relabel 算法不维护传统的流守恒，而是为每个顶点维持一个预流（允许流入量大于流出量）和一个高度标签。它通过两种基本操作推进流量：

  • 推送（Push）：将顶点 \(u\) 的盈余流量沿残留网络的可行边（即 \(h(u) = h(v) + 1\) 且该边有剩余容量）推送给相邻顶点 \(v\)。
  • 重标（Relabel）：当顶点 \(u\) 有盈余流量但无法推送时，将其高度提升到其邻居最低高度加 1。

最终，所有盈余流量要么被推回源点，要么到达汇点，从而得到最大流。

2. 引入 FIFO 顶点选择策略

在基础 Push-Relabel 中，顶点选择顺序会影响效率。FIFO 策略维护一个先进先出队列来存放有盈余的顶点（源点和汇点除外）。

  • 初始时，从源点向所有相邻顶点推送尽可能多的流量，将因此获得盈余的邻居加入队列。
  • 每次从队列头部取出一个顶点 \(u\)，不断对其执行推送和重标操作，直到其盈余清零或无法继续。
  • 如果推送使新顶点 \(v\) 获得盈余且 \(v\) 不在队列中（且 \(v\) 非源、汇），则将 \(v\) 加入队列尾部。
  • 当 \(u\) 的盈余变为零或操作无法进行时，如果 \(u\) 仍有盈余，则将其重新加入队列尾部（以便后续处理）。
  • 队列空时算法终止。
    FIFO 顺序避免了随机选择带来的低效，实践中表现良好。

3. 全局重标（Global Relabeling）优化

随着算法进行，某些顶点的高度标签可能过时，导致大量无效的重标操作。全局重标定期（例如每 \(n\) 次推送后）从汇点 \(t\) 开始，沿残留网络的反向边进行 BFS，重新计算每个顶点到汇点的真实最短距离（以剩余容量 >0 的边为单位长度），并以此作为新高度。

  • 这保证了高度是有效的下界，减少不必要的重标。
  • 复杂度上，每次全局重标需 \(O(m)\)，但显著减少总操作次数，整体更快。

4. 算法步骤详解

设图有 \(n\) 个顶点，\(m\) 条边，源为 \(s\)，汇为 \(t\)。

  1. 初始化：

    • 对每条边 \((u,v)\)，设置流量 \(f(u,v) = 0\)。
    • 对每个顶点 \(u\)：
      • 高度 \(h(u) = 0\)。
      • 盈余 \(e(u) = 0\)。
    • \(h(s) = n\)。
    • 对每条从 \(s\) 出发的边 \((s,v)\)，执行推送：推送量 \(\Delta = c(s,v)\)，更新 \(f(s,v) = \Delta\)，\(e(v) = \Delta\)，将 \(v\) 加入队列。
    • 初始化全局重标计数器（例如 push_count = 0）。

  2. 主循环（队列非空时）：

    • 从队列头部取出顶点 \(u\)。
    • 当 \(e(u) > 0\)：
      • 遍历 \(u\) 的每条出边（在残留网络中）：
        • 若 \(h(u) = h(v) + 1\) 且边有剩余容量 \(r > 0\)：
          • 执行推送：\(\Delta = \min(e(u), r)\)，更新流量和盈余。
          • 若 \(v \notin \{s,t\}\) 且推送后 \(e(v) = \Delta\)（原来为 0），则将 \(v\) 加入队列尾部。
          • push_count++。
          • 若 push_count >= n，执行全局重标：
            • 从 \(t\) 开始 BFS 计算各点到 \(t\) 的最短距离（忽略高度条件，只看剩余容量 >0 的边）。
            • 更新 \(h(u) = \text{distance}(u, t)\)。
            • 重置 push_count = 0。
      • 若遍历后 \(e(u) > 0\)：
        • 执行重标：\(h(u) = 1 + \min\{ h(v) \mid (u,v) \text{ 在残留网络中有剩余容量} \}\)。
        • 若重标后仍无法推送（无边可推），继续循环，直到 \(e(u) = 0\) 或可推。
    • 若退出内层循环时 \(e(u) > 0\)，将 \(u\) 重新加入队列尾部。

  3. 终止：

    • 队列空时，算法结束。此时汇点 \(t\) 无法再接收更多流量（或盈余全在 \(s\) 和 \(t\) 之间平衡）。
    • 最大流值为从 \(s\) 出发的流量总和，或进入 \(t\) 的流量总和。

5. 复杂度分析

  • 无优化时，Push-Relabel 最坏 \(O(n^2 m)\)。
  • 加入 FIFO 顺序后，可证 \(O(n^3)\)。
  • 再加入全局重标，实践中可达 \(O(n^2 \sqrt{m})\) 或更好，接近 Dinic 算法效率，对某些图更快。
  • 注意：全局重标 BFS 本身 \(O(m)\)，但减少总重标和推送次数。

6. 关键点总结

  • 核心机制：高度差推动流量，允许暂时违反流守恒。
  • FIFO 队列：避免饥饿，均衡处理盈余顶点。
  • 全局重标：定期“校正”高度，大幅加速。
  • 适用：适合稠密图或不规则图，实践中与 Dinic 齐名。

这个优化版本在实际最大流库中常见，是经典 Push-Relabel 的高效实现之一。

最大流问题的 FIFO 顶点高度重标算法（FIFO Push-Relabel with Global Relabeling 优化） 题目描述 ： 给定一个有向图，每条边有一个非负容量。指定一个源点 \( s \) 和一个汇点 \( t \)，求解从 \( s \) 到 \( t \) 的最大流量。我们使用基于 顶点高度重标 （Push-Relabel）框架的算法，并引入两种关键优化： 先进先出（FIFO） 的顶点选择顺序，以及周期性的 全局重标 （Global Relabeling）。请讲解这个算法的原理、步骤和复杂度。 解题过程循序渐进讲解 ： 1. 回顾 Push-Relabel 算法的基本思想 Push-Relabel 算法不维护传统的流守恒，而是为每个顶点维持一个 预流 （允许流入量大于流出量）和一个 高度标签 。它通过两种基本操作推进流量： 推送 （Push）：将顶点 \( u \) 的盈余流量沿残留网络的可行边（即 \( h(u) = h(v) + 1 \) 且该边有剩余容量）推送给相邻顶点 \( v \)。 重标 （Relabel）：当顶点 \( u \) 有盈余流量但无法推送时，将其高度提升到其邻居最低高度加 1。 最终，所有盈余流量要么被推回源点，要么到达汇点，从而得到最大流。 2. 引入 FIFO 顶点选择策略 在基础 Push-Relabel 中，顶点选择顺序会影响效率。FIFO 策略维护一个 先进先出队列 来存放有盈余的顶点（源点和汇点除外）。 初始时，从源点向所有相邻顶点推送尽可能多的流量，将因此获得盈余的邻居加入队列。 每次从队列头部取出一个顶点 \( u \)，不断对其执行推送和重标操作，直到其盈余清零或无法继续。 如果推送使新顶点 \( v \) 获得盈余且 \( v \) 不在队列中（且 \( v \) 非源、汇），则将 \( v \) 加入队列尾部。 当 \( u \) 的盈余变为零或操作无法进行时，如果 \( u \) 仍有盈余，则将其重新加入队列尾部（以便后续处理）。 队列空时算法终止。 FIFO 顺序避免了随机选择带来的低效，实践中表现良好。 3. 全局重标（Global Relabeling）优化 随着算法进行，某些顶点的高度标签可能过时，导致大量无效的重标操作。 全局重标 定期（例如每 \( n \) 次推送后）从汇点 \( t \) 开始，沿残留网络的反向边进行 BFS，重新计算每个顶点到汇点的真实最短距离（以剩余容量 >0 的边为单位长度），并以此作为新高度。 这保证了高度是有效的下界，减少不必要的重标。 复杂度上，每次全局重标需 \( O(m) \)，但显著减少总操作次数，整体更快。 4. 算法步骤详解 设图有 \( n \) 个顶点，\( m \) 条边，源为 \( s \)，汇为 \( t \)。 初始化 ： 对每条边 \((u,v)\)，设置流量 \( f(u,v) = 0 \)。 对每个顶点 \( u \)： 高度 \( h(u) = 0 \)。 盈余 \( e(u) = 0 \)。 \( h(s) = n \)。 对每条从 \( s \) 出发的边 \((s,v)\)，执行推送：推送量 \( \Delta = c(s,v) \)，更新 \( f(s,v) = \Delta \)，\( e(v) = \Delta \)，将 \( v \) 加入队列。 初始化全局重标计数器（例如 push_count = 0 ）。 主循环 （队列非空时）： 从队列头部取出顶点 \( u \)。 当 \( e(u) > 0 \)： 遍历 \( u \) 的每条出边（在残留网络中）： 若 \( h(u) = h(v) + 1 \) 且边有剩余容量 \( r > 0 \)： 执行推送：\( \Delta = \min(e(u), r) \)，更新流量和盈余。 若 \( v \notin \{s,t\} \) 且推送后 \( e(v) = \Delta \)（原来为 0），则将 \( v \) 加入队列尾部。 push_count++ 。 若 push_count >= n ，执行 全局重标 ： 从 \( t \) 开始 BFS 计算各点到 \( t \) 的最短距离（忽略高度条件，只看剩余容量 >0 的边）。 更新 \( h(u) = \text{distance}(u, t) \)。 重置 push_count = 0 。 若遍历后 \( e(u) > 0 \)： 执行重标：\( h(u) = 1 + \min\{ h(v) \mid (u,v) \text{ 在残留网络中有剩余容量} \} \)。 若重标后仍无法推送（无边可推），继续循环，直到 \( e(u) = 0 \) 或可推。 若退出内层循环时 \( e(u) > 0 \)，将 \( u \) 重新加入队列尾部。 终止 ： 队列空时，算法结束。此时汇点 \( t \) 无法再接收更多流量（或盈余全在 \( s \) 和 \( t \) 之间平衡）。 最大流值为从 \( s \) 出发的流量总和，或进入 \( t \) 的流量总和。 5. 复杂度分析 无优化时，Push-Relabel 最坏 \( O(n^2 m) \)。 加入 FIFO 顺序后，可证 \( O(n^3) \)。 再加入全局重标，实践中可达 \( O(n^2 \sqrt{m}) \) 或更好，接近 Dinic 算法效率，对某些图更快。 注意：全局重标 BFS 本身 \( O(m) \)，但减少总重标和推送次数。 6. 关键点总结 核心机制：高度差推动流量，允许暂时违反流守恒。 FIFO 队列：避免饥饿，均衡处理盈余顶点。 全局重标：定期“校正”高度，大幅加速。 适用：适合稠密图或不规则图，实践中与 Dinic 齐名。 这个优化版本在实际最大流库中常见，是经典 Push-Relabel 的高效实现之一。