福特-富克森算法

福特-富克森（Ford-Fulkerson）算法是一种求解最大流问题的经典算法，它的基本思想是通过不断地增广路径来找到最大流。

最大流问题通常是指在网络中找到从源点到汇点的最大流量，其中网络由若干条有向边组成，每条边都有一个容量，表示该边可以通过的最大流量。最大流问题的目标是找到一个流，使得从源点到汇点的总流量最大。

福特-富克森算法的主要思想是从源点开始，寻找一条增广路径，并增加该路径上的流量，重复这个过程，直到没有增广路径为止。增广路径是一条从源点到汇点的路径，其上每一条边都还有剩余容量，即可以增加流量。

福特-富克森算法包括以下步骤：

1. 从源点开始，初始化所有边的流量为0。

2. 寻找增广路径：在残留网络（剩余容量大于0的边组成的网络）中找到一条从源点到汇点的增广路径，即一条路径上所有边的剩余容量均大于0。

3. 计算增广量：增广路径上的最小剩余容量即为增广量。

4. 更新流量：将增广路径上的所有边的流量增加增广量。

5. 更新残留网络：对于每条增广路径上的边，减少其剩余容量，同时增加其反向边的剩余容量。

6. 重复步骤2到步骤5，直到没有增广路径为止。

福特-富克森算法的时间复杂度取决于增广路径的查找方法。常用的增广路径查找方法包括广度优先搜索和深度优先搜索，时间复杂度分别为O(VE)和O(E^2)，其中V和E分别表示网络的节点数和边数。