xxx 最大流问题（Ford-Fulkerson 方法中的 Edmonds-Karp 算法） 题目描述 给定一个有向图，其中每条边有一个非负容量（capacity），以及一个源点（source）和一个汇点（sink）。最大流问题的目标是找到从源点到汇点的最大流量，使得每条边上的流量不超过其容量，且除源点和汇点外，每个顶点的流入流量等于流出流量（流量守恒）。 解题过程 基本概念 流量网络：有向图 \( G = (V, E) \)，边容量 \( c(u, v) \geq 0 \)，源点 \( s \)，汇点 \( t \)。 可行流：满足容量限制（流量不超过容量）和流量守恒（中间节点流入等于流出）。 最大流：从 \( s \) 到 \( t \) 的最大可行流量值。 Ford-Fulkerson 方法的核心思想 通过不断寻找增广路径（Augmenting Path）来增加流量。 增广路径是残量网络中一条从 \( s \) 到 \( t \) 的路径，残量容量（剩余可用的容量）均大于零。 每次沿增广路径增加流量后，更新残量网络（正向边减少容量，反向边增加容量）。 Edmonds-Karp 算法的改进 问题：Ford-Fulkerson 使用 DFS 寻找增广路径，可能效率低下（例如容量为无理数时可能不终止）。 改进：使用 BFS 寻找增广路径，确保每次选择最短路径（边数最少）。 优势：BFS 保证算法在 \( O(|V| \cdot |E|^2) \) 时间内终止。 算法步骤 步骤 1：初始化 设置初始流量 \( f(u, v) = 0 \) 对所有边 \( (u, v) \)。 构建残量网络 \( G_ f \)，其中每条边的残量容量为 \( c_ f(u, v) = c(u, v) - f(u, v) \)，并添加反向边 \( c_ f(v, u) = f(u, v) \)。 步骤 2：循环寻找增广路径 使用 BFS 在残量网络中寻找从 \( s \) 到 \( t \) 的最短路径（按边数计算）。 若找不到路径，算法终止，当前流量即为最大流。 若找到路径，计算路径上的最小残量容量（瓶颈值）： \[ \Delta = \min\{ c_ f(u, v) \mid (u, v) \in \text{路径} \} \] 步骤 3：更新流量和残量网络 对路径上的每条边 \( (u, v) \)： 减少正向边残量容量：\( c_ f(u, v) \gets c_ f(u, v) - \Delta \)。 增加反向边残量容量：\( c_ f(v, u) \gets c_ f(v, u) + \Delta \)。 总流量增加 \( \Delta \)。 步骤 4：重复 返回步骤 2，直到无法找到增广路径。 实例演示 考虑一个简单网络： 顶点：\( s, A, B, t \) 边容量：\( (s, A): 3, (s, B): 2, (A, B): 1, (A, t): 2, (B, t): 3 \) 过程： BFS 找到路径 \( s \to A \to t \)，瓶颈 \( \Delta = 2 \)，更新流量为 2。 BFS 找到路径 \( s \to B \to t \)，瓶颈 \( \Delta = 2 \)，更新流量为 4。 BFS 找到路径 \( s \to A \to B \to t \)，瓶颈 \( \Delta = 1 \)，更新流量为 5（最大流）。 为什么算法正确 BFS 保证每次增广路径最短，避免陷入低效路径。 最大流最小割定理保证算法找到的流是最优的。 复杂度分析 每次 BFS 耗时 \( O(|E|) \)。 最多增广 \( O(|V| \cdot |E|) \) 次（因为每次增广会使最短路径长度增加）。 总复杂度：\( O(|V| \cdot |E|^2) \)。 总结 Edmonds-Karp 算法通过 BFS 优化增广路径的选择，确保了高效性和终止性，是最大流问题的基础解法之一。