Edmonds-Karp最大流算法

图算法

Edmonds-Karp算法是Ford-Fulkerson算法的一个实现,使用广度优先搜索(BFS)来寻找最短增广路径,从而计算网络流中从源点到汇点的最大流量。

时间复杂度:最佳 O(V × E) | 平均 O(V × E²) | 最差 O(V × E²)
空间复杂度:O(V + E)
图类型:有向图

应用场景/前提条件

  • 网络流
  • 增广路径
  • 广度优先搜索

算法讲解

Edmonds-Karp最大流算法

介绍

Edmonds-Karp算法是一种用于解决网络最大流问题的经典算法,它是Ford-Fulkerson方法的一种特殊实现。最大流问题是在一个流网络中,确定从源点(source)到汇点(sink)之间的最大可能流量。Edmonds-Karp算法的核心思想是使用广度优先搜索(BFS)来寻找增广路径,这保证了算法的时间复杂度为O(V·E²),其中V是顶点数,E是边数。

算法步骤

  1. 初始化流网络,所有边的流量都为0
  2. 使用BFS寻找从源点到汇点的一条增广路径
  3. 计算该路径上的可增加流量(即路径上所有边的剩余容量的最小值)
  4. 沿着这条路径增加流量
  5. 重复步骤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

...