Ford-Fulkerson最大流算法

图算法

Ford-Fulkerson算法是一种用于计算网络流中最大流的迭代方法。它通过反复寻找增广路径并增加路径上的流量,直到无法找到更多的增广路径为止。

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

应用场景/前提条件

  • 网络流
  • 增广路径
  • 最大流最小割定理

算法讲解

Ford-Fulkerson最大流算法

介绍

Ford-Fulkerson算法是一种用于解决网络流问题中最大流问题的经典算法,由L. R. Ford Jr.和D. R. Fulkerson于1956年提出。最大流问题是指在一个有向图中,给定源点(source)和汇点(sink),求从源点到汇点的最大可能流量。算法基于增广路径(augmenting path)的概念,通过不断寻找并增加流量直到无法找到更多增广路径为止。

算法步骤

  1. 初始化网络中所有边的流量为0
  2. 在残余网络中寻找一条从源点到汇点的增广路径
  3. 计算该路径上可以增加的最大流量(即路径上所有边的剩余容量的最小值)
  4. 更新路径上所有边的流量以及对应反向边的流量
  5. 重复步骤2-4,直到无法找到更多的增广路径为止

算法详解

假设有一个流网络,包含6个节点(0-5),其中0为源点,5为汇点,边的容量关系如下:

  • 边(0,1)容量为16
  • 边(0,2)容量为13
  • 边(1,2)容量为10
  • 边(1,3)容量为12
  • 边(2,1)容量为4
  • 边(2,4)容量为14

...