最大流问题（Edmonds-Karp 算法）
字数 1750 2025-11-28 14:32:57

最大流问题（Edmonds-Karp 算法）

题目描述
给定一个有向图 \(G = (V, E)\)，其中每条边 \((u, v) \in E\) 有一个非负容量 \(c(u, v) \geq 0\)。图中有一个源点 \(s\) 和一个汇点 \(t\)。最大流问题的目标是找到从 \(s\) 到 \(t\) 的最大流量，即满足以下条件的流函数 \(f(u, v)\)：

  1. 容量约束：对任意边 \((u, v)\)，\(0 \leq f(u, v) \leq c(u, v)\)。
  2. 流量守恒：对任意非源非汇顶点 \(u\)，流入 \(u\) 的总流量等于流出 \(u\) 的总流量。
    Edmonds-Karp 算法是 Ford-Fulkerson 方法的一种实现，通过 广度优先搜索（BFS） 寻找增广路径，确保算法在多项式时间内收敛。

解题过程

1. 基本概念：残量图与增广路径

  • 残量图 \(G_f\)：在原图基础上，为每条边 \((u, v)\) 添加反向边 \((v, u)\)。边的残量容量定义为：
    • 正向边：\(c_f(u, v) = c(u, v) - f(u, v)\)（剩余可用的容量）。
    • 反向边：\(c_f(v, u) = f(u, v)\)（可撤销的流量）。
  • 增广路径：在残量图中从 \(s\) 到 \(t\) 的一条路径，路径上所有边的残量容量均大于零。通过该路径可以增加流量。

2. 算法步骤

  • 步骤 1：初始化流 \(f(u, v) = 0\) 对所有边。
  • 步骤 2：循环执行以下操作直到无法找到增广路径：
    a. 使用 BFS 在残量图 \(G_f\) 中寻找从 \(s\) 到 \(t\) 的最短路径（按边数计算）。
    b. 若找到路径 \(P\)，计算路径上的最小残量容量：

\[ \Delta = \min\{c_f(u, v) \mid (u, v) \in P\}. \]

c. 对路径上的每条边更新流量：  
   - 若为正向边：$ f(u, v) \leftarrow f(u, v) + \Delta $。  
   - 若为反向边：$ f(v, u) \leftarrow f(v, u) - \Delta $（相当于减少正向流量）。
  • 步骤 3：返回总流量 \(\sum_{v \in V} f(s, v)\)。

3. 关键点：为什么用 BFS？

  • Ford-Fulkerson 的 DFS 实现可能因某些输入陷入指数级复杂度（例如，边容量为无理数时）。
  • Edmonds-Karp 通过 BFS 保证每次找到的增广路径是 最短路径（边数最少），从而确保算法在 \(O(|V| \cdot |E|^2)\) 时间内结束。

4. 示例演示
考虑一个简单图：

  • 顶点：\(s, a, b, t\)
  • 边容量：\((s, a): 3, (s, b): 2, (a, b): 1, (a, t): 2, (b, t): 3\)
    执行过程：
  1. 初始流为 0。
  2. 第一次 BFS 找到路径 \(s \to a \to t\)，最小残量 \(\Delta = 2\)，更新流量。
  3. 第二次 BFS 找到路径 \(s \to b \to t\)，\(\Delta = 2\)，更新流量。
  4. 第三次 BFS 找到路径 \(s \to a \to b \to t\)，\(\Delta = 1\)，更新流量。
  5. 无法再找到增广路径，总流量为 \(2 + 2 + 1 = 5\)。

5. 复杂度分析

  • 每次 BFS 耗时 \(O(|E|)\)。
  • 最多执行 \(O(|V| \cdot |E|)\) 次增广（因为每次增广至少使一条边达到饱和，且最短路径长度单调递增）。
  • 总复杂度：\(O(|V| \cdot |E|^2)\)。

总结
Edmonds-Karp 算法通过 BFS 寻找最短增广路径，保证了高效性和可靠性，是理解最大流问题的基础。其核心在于残量图的构建与流量更新规则，通过反向边允许“撤销”流量，从而找到全局最优解。

最大流问题（Edmonds-Karp 算法） 题目描述 给定一个有向图 \( G = (V, E) \)，其中每条边 \( (u, v) \in E \) 有一个非负容量 \( c(u, v) \geq 0 \)。图中有一个源点 \( s \) 和一个汇点 \( t \)。最大流问题的目标是找到从 \( s \) 到 \( t \) 的最大流量，即满足以下条件的流函数 \( f(u, v) \)： 容量约束 ：对任意边 \( (u, v) \)，\( 0 \leq f(u, v) \leq c(u, v) \)。 流量守恒 ：对任意非源非汇顶点 \( u \)，流入 \( u \) 的总流量等于流出 \( u \) 的总流量。 Edmonds-Karp 算法是 Ford-Fulkerson 方法的一种实现，通过 广度优先搜索（BFS） 寻找增广路径，确保算法在多项式时间内收敛。 解题过程 1. 基本概念：残量图与增广路径 残量图 \( G_ f \)：在原图基础上，为每条边 \( (u, v) \) 添加反向边 \( (v, u) \)。边的残量容量定义为： 正向边：\( c_ f(u, v) = c(u, v) - f(u, v) \)（剩余可用的容量）。 反向边：\( c_ f(v, u) = f(u, v) \)（可撤销的流量）。 增广路径 ：在残量图中从 \( s \) 到 \( t \) 的一条路径，路径上所有边的残量容量均大于零。通过该路径可以增加流量。 2. 算法步骤 步骤 1 ：初始化流 \( f(u, v) = 0 \) 对所有边。 步骤 2 ：循环执行以下操作直到无法找到增广路径： a. 使用 BFS 在残量图 \( G_ f \) 中寻找从 \( s \) 到 \( t \) 的最短路径（按边数计算）。 b. 若找到路径 \( P \)，计算路径上的最小残量容量： \[ \Delta = \min\{c_ f(u, v) \mid (u, v) \in P\}. \] c. 对路径上的每条边更新流量： 若为正向边：\( f(u, v) \leftarrow f(u, v) + \Delta \)。 若为反向边：\( f(v, u) \leftarrow f(v, u) - \Delta \)（相当于减少正向流量）。 步骤 3 ：返回总流量 \( \sum_ {v \in V} f(s, v) \)。 3. 关键点：为什么用 BFS？ Ford-Fulkerson 的 DFS 实现可能因某些输入陷入指数级复杂度（例如，边容量为无理数时）。 Edmonds-Karp 通过 BFS 保证每次找到的增广路径是 最短路径 （边数最少），从而确保算法在 \( O(|V| \cdot |E|^2) \) 时间内结束。 4. 示例演示 考虑一个简单图： 顶点：\( s, a, b, t \) 边容量：\( (s, a): 3, (s, b): 2, (a, b): 1, (a, t): 2, (b, t): 3 \) 执行过程 ： 初始流为 0。 第一次 BFS 找到路径 \( s \to a \to t \)，最小残量 \( \Delta = 2 \)，更新流量。 第二次 BFS 找到路径 \( s \to b \to t \)，\( \Delta = 2 \)，更新流量。 第三次 BFS 找到路径 \( s \to a \to b \to t \)，\( \Delta = 1 \)，更新流量。 无法再找到增广路径，总流量为 \( 2 + 2 + 1 = 5 \)。 5. 复杂度分析 每次 BFS 耗时 \( O(|E|) \)。 最多执行 \( O(|V| \cdot |E|) \) 次增广（因为每次增广至少使一条边达到饱和，且最短路径长度单调递增）。 总复杂度：\( O(|V| \cdot |E|^2) \)。 总结 Edmonds-Karp 算法通过 BFS 寻找最短增广路径，保证了高效性和可靠性，是理解最大流问题的基础。其核心在于残量图的构建与流量更新规则，通过反向边允许“撤销”流量，从而找到全局最优解。