Ford-Fulkerson算法求最大流

算法概述

Ford-Fulkerson算法是一种用于解决网络最大流问题的经典方法。该算法基于增广路径的概念，通过不断寻找从源点到汇点的可行流路径来逐步增加流量，直到无法再找到新的增广路径为止。最终得到的就是该网络的最大流。

算法步骤

1. 初始化

• 构建一个初始可行流 $f$。
• 初始时，所有边的流量为0。

2. 寻找增广路径

使用深度优先搜索（DFS）或广度优先搜索（BFS）寻找从源点到汇点的一条增广路径。该路径上的每一条边要么还剩余容量可以增加流，要么在反向边上还有正的残余流量。

3. 调整流量

找到一条增广路径后，根据这条路径的最小残余容量（即当前路径上最小的可增加的流值），调整沿途所有相关边上的流量。同时更新残余网络中的边容量信息，并将这些边的流量在原图中逆向记录下来。

4. 更新可行流

重复步骤2和3，直到无法找到任何增广路径为止。

算法实现

Ford-Fulkerson算法可以采用多种方式实现，其中一种简单且直观的方法是使用BFS来寻找增广路径。具体步骤如下：

1. 初始化：创建一个初始可行流 $f$，所有边的流量为0。
2. 构建残余网络：根据当前网络和可行流 $f$ 构建残余网络 $G_f = (V, E_f)$，其中每条边 $(u, v) \in E$ 有正的残余容量，则在残留网络中存在一条从 $u$ 到 $v$ 的边。
3. 使用BFS找增广路径：使用BFS从源点开始遍历残余网络，寻找汇点。如果找到汇点，则找到了一条增广路径；否则继续遍历直至无法再找到新的路径。
4. 调整流量：根据找到的增广路径上的最小容量值来调整原图中的流值，并更新残余网络中的边容量信息。
5. 重复步骤3和4，直到BFS找不到从源点到汇点的路径为止。

复杂性分析

Ford-Fulkerson算法的时间复杂度依赖于实现细节及增广路径的选择方法。在最坏情况下，算法可能需要执行多项式次增广操作，但具体次数与网络的具体结构有关。如果采用Dijkstra或BFS来选择增广路径，则时间复杂度可以被优化到 $O(E \times F)$，其中 $E$ 是边的数量，而 $F$ 则是最大流的值。

示例

假设有一个简单的网络图，源点为S，汇点为T，包含如下有向边及其容量：

• S -> A: 5
• S -> B: 3
• A -> C: 4
• B -> C: 2
• B -> T: 10
• A -> T: 6

初始状态

• $f_{S->A} = 0$
• $f_{S->B} = 0$
• $f_{A->C} = 0$
• $f_{B->C} = 0$
• $f_{B->T} = 0$
• $f_{A->T} = 0$

第一步增广

• 增广路径：S -> A -> C -> T，最小容量为4。
• 更新流：
  • $f_{S->A} = 4$
  • $f_{A->C} = 4$
  • $f_{C->T} = 4$

第二步增广

• 增广路径：S -> B -> C -> T，最小容量为2。
• 更新流：
  • $f_{S->B} = 2$
  • $f_{B->C} = 2$
  • $f_{C->T} = 6$

第三步增广

• 增广路径：S -> B -> T，最小容量为8。
• 更新流：
  • $f_{S->B} = 10$
  • $f_{B->T} = 8$

此时网络最大流为 $4 + 6 + 8 = 18$。

结论

Ford-Fulkerson算法是求解网络最大流问题的重要工具之一。它通过不断寻找增广路径来逐步增加流值，直至无法找到新的增广路径为止。虽然在最坏情况下可能需要多次增广操作，但其思想和实现方法简单直观，在理论和实际应用中具有重要意义。