Edmonds-Karp最大流算法
介绍
Edmonds-Karp算法是一种用于解决网络最大流问题的经典算法,它是Ford-Fulkerson方法的一种特殊实现。最大流问题是在一个流网络中,确定从源点(source)到汇点(sink)之间的最大可能流量。Edmonds-Karp算法的核心思想是使用广度优先搜索(BFS)来寻找增广路径,这保证了算法的时间复杂度为O(V·E²),其中V是顶点数,E是边数。
算法步骤
- 初始化流网络,所有边的流量都为0
- 使用BFS寻找从源点到汇点的一条增广路径
- 计算该路径上的可增加流量(即路径上所有边的剩余容量的最小值)
- 沿着这条路径增加流量
- 重复步骤2-4,直到找不到增广路径为止
算法详解
假设有一个包含6个顶点(S, A, B, C, D, T)的流网络,S为源点,T为汇点,边的容量如下:
- S到A,容量为10
- S到C,容量为10
- A到B,容量为4
- A到C,容量为2
- A到D,容量为8
- B到T,容量为10
...