Ford-Fulkerson方法（最大流问题）

Ford-Fulkerson方法是解决网络流中最大流问题的经典算法。它用于计算从源点（source）到汇点（sink）在一个有向图中能通过的最大流量，其中每条边都有一个容量限制。

核心概念

• 流网络（Flow Network）：一个有向图G=(V, E)，其中每条边(u, v)有一个非负容量c(u, v)≥0。包含一个源点s和一个汇点t。
• 流（Flow）：一个函数f: V×V → ℝ，满足：
  1. 容量限制：对于所有边，0 ≤ f(u, v) ≤ c(u, v)。
  2. 流量守恒：对于所有非源非汇的顶点，流入的流量等于流出的流量。
• 残留网络（Residual Network）：给定流网络G和流f，残留网络G_f由原图的边和反向边组成。对于每条边(u, v)：
  • 前向边的残留容量为c(u, v) - f(u, v)。
  • 反向边的残留容量为f(u, v)（表示可减少的流量）。
• 增广路径（Augmenting Path）：在残留网络G_f中，从s到t的一条简单路径，路径上所有边的残留容量均大于0。

算法步骤

1. 初始化：初始流f设为0（所有边流量为0）。
2. 构建残留网络：根据当前流f，计算残留网络G_f。
3. 寻找增广路径：在G_f中寻找一条从s到t的路径，路径上最小残留容量（瓶颈容量）>0。若找不到路径，算法终止。
4. 增广流：沿找到的路径增加流量，增加量为路径的瓶颈容量。同时更新残留网络（前向边减少容量，反向边增加容量）。
5. 重复：重复步骤2-4，直到无法找到增广路径。

详细示例
考虑一个简单流网络：

• 顶点：s, A, B, t
• 边与容量：(s→A, 10), (s→B, 10), (A→B, 5), (A→t, 15), (B→t, 10)

步骤1：初始化流
所有边流量初始为0。

步骤2：第一次迭代

• 残留网络G_f与原图相同（因流为0）。
• 找增广路径：s→A→t，瓶颈容量=min(10, 15)=10。
• 增广流：沿路径增加流量10。更新：
  • 边s→A流量=10，残留容量=0（前向边耗尽），添加反向边A→s容量10。
  • 边A→t流量=10，残留容量=5，添加反向边t→A容量10。

步骤3：第二次迭代

• 当前残留网络包含边：s→B(10), A→B(5), A→t(5), B→t(10), 及反向边A→s(10)等。
• 找增广路径：s→B→t，瓶颈容量=min(10, 10)=10。
• 增广流：增加流量10。更新：
  • s→B流量=10，残留容量=0；添加反向边B→s容量10。
  • B→t流量=10，残留容量=0；添加反向边t→B容量10。

步骤4：第三次迭代

• 残留网络中，从s出发只有s→A已满，但可通过反向边A→B寻找路径：s→B→A→t。
  • 路径：s→B（残留容量0，但反向边B→A容量0？注意A→B有容量5，但方向不符。正确路径应为s→A→B→t）。
• 详细检查残留边：
  • s→A: 容量0，但反向边A→s容量10（可减少流）。
  • A→t: 残留容量5。
  • s→B: 容量0，反向边B→s容量10。
  • B→t: 容量0，反向边t→B容量10。
  • A→B: 容量5（前向边未满）。
• 增广路径：s→A→B→t。瓶颈容量=min(通过A→s的反向边？错误。应直接使用残留容量：s→A已满，但残留网络中有反向边A→s容量10，表示可减少流，但增广路径需正残留容量。正确路径：s→A→B→t的残留容量计算：
  • s→A: 残留容量0，但考虑反向边？不，应使用残留容量：实际路径为s→B→A→t？重新选择：从s出发，s→B已满，但s→A已满。此时应使用反向边：路径s→B→A→t：
    • s→B: 残留容量0，但反向边B→s不存在？错误。正确残留网络：
      • 边A→B: 容量5，流0，残留容量5。
      • 路径s→A→B→t：s→A残留容量0（失败）。路径s→B→A→t：s→B残留容量0（失败）。因此无增广路径？实际上，最大流应为20（s→A→t流10，s→B→t流10），算法终止。

最大流值：总流出s的流量=10+10=20。

算法复杂度

• 时间复杂度：O(E * max_flow)，其中max_flow为最大流值。若容量为整数，算法保证终止，但若容量极大或为无理数时可能不收敛。
• 优化：使用Edmonds-Karp算法（BFS寻找增广路径），复杂度为O(V E²)。

关键点

• 反向边允许算法撤销先前分配的流，确保找到全局最优解。
• 算法终止时，最小割（min-cut）的容量等于最大流值（最大流最小割定理）。

通过逐步增广，Ford-Fulkerson方法能有效求解最大流问题，是网络流算法的基础。