最大流问题（Goldberg-Rao算法）
字数 1021 2025-11-03 08:34:44

最大流问题（Goldberg-Rao算法）

题目描述
给定一个有向图，其中每条边有一个非负容量（capacity），以及一个源点（source）和一个汇点（sink），求从源点到汇点的最大流。Goldberg-Rao算法是一种高效的最大流算法，其时间复杂度为O(V²E log(V²/E) log U)，其中U是最大边容量。该算法结合了Push-Relabel的思想和最小割的概念，通过动态调整流和标签（label）来逐步逼近最大流。

解题过程

  1. 初始化

    • 设置初始流f为0（即每条边上的流为0）。
    • 为每个顶点分配一个高度（height）或标签（label），源点的高度设为V（顶点数），其他顶点的高度设为0。
    • 初始化每个顶点的超额流（excess flow）：源点的超额流为无穷大（实际中设为一个大数），其他顶点为0。

  2. 定义距离函数和最小割

    • 使用广度优先搜索（BFS）从汇点计算每个顶点到汇点的距离（距离标签d(v)）。
    • 根据距离标签，将边分为允许边（admissible edges）：即满足d(u) = d(v) + 1的边(u,v)。
    • 通过距离标签定义最小割，并计算初始残差图（residual graph）。

  3. 流推进（Push）操作

    • 选择有正超额流的顶点u。
    • 尝试沿允许边(u,v)推进流：推进量为min(超额流, 残差容量)。
    • 如果推进后边(u,v)的残差容量为0，则从残差图中移除该边。

  4. 标签更新（Relabel）操作

    • 如果顶点u有超额流，但没有允许边可推进，则更新其距离标签：d(u) = min{d(v) + 1 | (u,v)是残差边}。
    • 这保证算法始终有进展，避免死循环。

  5. 阶段处理（Phase Processing）

    • 将算法分为多个阶段，每个阶段使用固定的距离标签。
    • 在每个阶段内，反复执行Push和Relabel操作，直到没有顶点有超额流（除源点和汇点）。
    • 阶段结束后，重新计算距离标签（通过BFS从汇点），并开始新阶段。

  6. 终止条件

    • 当源点的距离标签d(s) ≥ V时，说明已找到最大流，算法终止。
    • 最终，汇点的流入量即为最大流值。

关键点

  • Goldberg-Rao算法通过距离标签和阶段划分，减少不必要的操作，比传统Push-Relabel更高效。
  • 每个阶段保证流至少增加一个单位，确保算法在多项式时间内收敛。
  • 实际实现中需用优先队列管理超额流顶点，优化性能。

通过以上步骤，算法逐步调整流和标签，最终得到最大流。

最大流问题（Goldberg-Rao算法） 题目描述 给定一个有向图，其中每条边有一个非负容量（capacity），以及一个源点（source）和一个汇点（sink），求从源点到汇点的最大流。Goldberg-Rao算法是一种高效的最大流算法，其时间复杂度为O(V²E log(V²/E) log U)，其中U是最大边容量。该算法结合了Push-Relabel的思想和最小割的概念，通过动态调整流和标签（label）来逐步逼近最大流。 解题过程 初始化 设置初始流f为0（即每条边上的流为0）。 为每个顶点分配一个高度（height）或标签（label），源点的高度设为V（顶点数），其他顶点的高度设为0。 初始化每个顶点的超额流（excess flow）：源点的超额流为无穷大（实际中设为一个大数），其他顶点为0。 定义距离函数和最小割 使用广度优先搜索（BFS）从汇点计算每个顶点到汇点的距离（距离标签d(v)）。 根据距离标签，将边分为允许边（admissible edges）：即满足d(u) = d(v) + 1的边(u,v)。 通过距离标签定义最小割，并计算初始残差图（residual graph）。 流推进（Push）操作 选择有正超额流的顶点u。 尝试沿允许边(u,v)推进流：推进量为min(超额流, 残差容量)。 如果推进后边(u,v)的残差容量为0，则从残差图中移除该边。 标签更新（Relabel）操作 如果顶点u有超额流，但没有允许边可推进，则更新其距离标签：d(u) = min{d(v) + 1 | (u,v)是残差边}。 这保证算法始终有进展，避免死循环。 阶段处理（Phase Processing） 将算法分为多个阶段，每个阶段使用固定的距离标签。 在每个阶段内，反复执行Push和Relabel操作，直到没有顶点有超额流（除源点和汇点）。 阶段结束后，重新计算距离标签（通过BFS从汇点），并开始新阶段。 终止条件 当源点的距离标签d(s) ≥ V时，说明已找到最大流，算法终止。 最终，汇点的流入量即为最大流值。 关键点 Goldberg-Rao算法通过距离标签和阶段划分，减少不必要的操作，比传统Push-Relabel更高效。 每个阶段保证流至少增加一个单位，确保算法在多项式时间内收敛。 实际实现中需用优先队列管理超额流顶点，优化性能。 通过以上步骤，算法逐步调整流和标签，最终得到最大流。