Ford-Fulkerson 方法

定义

Ford-Fulkerson 方法由 Lester Ford 与 Delbert Fulkerson 于 1956 年提出,用于求流网络中从源点到汇点的最大流,是网络流理论的奠基性算法框架。

原理

核心是残量网络与增广路径:只要能在残量网络中找到一条从源到汇的可行路径,就沿该路径增加流量,并相应更新正向边的剩余容量与反向边(允许"反悔"已有流量)。无增广路径时当前流即为最大流,这由最大流最小割定理保证。

实现与复杂度

用 BFS 选取最短增广路径的实现称 Edmonds-Karp 算法,复杂度 O(VE²);Dinic 算法引入分层图与阻塞流,达到 O(V²E),在实践中远快于理论界。

应用

二分图匹配、项目选择、图像分割(graph cut)、运输与管道网络容量规划等大量组合优化问题都可归约为最大流。