Ford-Fulkerson 算法
- 提出者
- Lester R. Ford and Delbert R. Fulkerson
- 年份
- 1956
- 类型
- algorithm
- 类别
- Graph Algorithms
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
Ford-Fulkerson 算法由 Lester R. Ford 和 Delbert R. Fulkerson 于 1956 年提出,是计算流网络中最大流的基础方法。它在具有边容量约束的有向图中,找出从源点到汇点可以传输的最大流量。
方法背后的直觉
该算法通过在残余网络中反复寻找从源点到汇点的增广路径来工作,其中每条边都有剩余容量。每条路径贡献的流量等于其瓶颈容量(路径上剩余容量最小的边)。该过程一直持续到不再存在增广路径为止,此时达到最大流。关键的洞察是最大流最小割定理:最大流等于网络中最小割的容量。
历史学
Ford 和 Fulkerson 于 1956 年提出了最大流问题及其开创性算法。这项工作具有革命性,既建立了一种算法方法,又确立了著名的最大流最小割定理。Edmonds 和 Karp (1972) 通过使用广度优先搜索进行路径选择,改进了最坏情况复杂度。Dinic、Karzanov 等人的后续进展带来了更快的算法,但 Ford-Fulkerson 方法仍然是计算机科学中经典且具有教学价值的算法。
何时使用
将 Ford-Fulkerson 算法应用于具有正整数容量的有向或无向流网络,以找到最大流。它适用于中小型网络,并能直观地理解网络流概念。对于非常大的网络或需要整数流的情况,可以考虑 Edmonds-Karp(使用 BFS)或 Dinic 算法以获得更好的最坏情况性能。当算法行为的理解与速度同样重要时使用。
局限与注意事项
- 时间复杂度取决于容量值(一般不是多项式的;对于无理数容量可能呈指数级增长)
- 如果容量是无理数,则可能不收敛(需要仔细实现有理数算术)
- 在大型网络上不如 Edmonds-Karp 或 Dinic 等专用算法高效
- 对增广路径的选择顺序敏感
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 基于增广路径的简单直观方法
- 当容量为有理数或整数时,保证得到最优解
- 对于具有小整数容量的网络效率高
- 构成了理解最大流最小割对偶性的理论基础
- 可用于有向图和无向图
应用
- 网络路由:在通信网络中最大化从源点到目的地的吞吐量
- 交通网络:在考虑道路和铁路约束的情况下,确定城市之间的最大货物容量
- 二分图匹配:通过构建流网络在二分图中找到最大匹配
- 图像分割:使用最大流算法将图像分割为前景和背景
- 航空公司调度:优化飞机路线以最大化通过枢纽辐射网络的乘客流量
- 蛋白质分析:计算生物网络中的最大流以理解相互作用通路
使用方式
使用方式
初始化残余图,使边容量等于原始边容量,所有边的流量为零。
在残余图中,使用深度优先搜索或广度优先搜索寻找从源点到汇点的增广路径,计算路径上的最小容量,并将此流量加到路径上的所有边,同时减小它们的残余容量。
重复增广,直到残余图中不存在增广路径;累积的总流量即为最大流。
常见陷阱
- 选择糟糕的增广路径,导致收敛缓慢或结果不正确
- 未能正确更新残余容量或添加反向边来撤销流量
- 在需要精确算术以保证正确性的情况下,使用了整数除法或浮点算术
常见问题
什么是最大流最小割定理?
该定理指出,从源点到汇点的最大流等于分隔源点和汇点的任何割的最小容量。这提供了理论洞察和流算法的验证方法。
为什么该算法有时收敛缓慢?
在不幸的路径选择下,即使可以进行更大的增广,算法也可能每次迭代只增广一个单位的流量。使用广度优先搜索(Edmonds-Karp)可确保多项式时间收敛。
该算法如何处理无向边?
将每条无向边替换为两条方向相反的有向边,两者具有相同的容量。然后,算法在有向网络中寻找流量。
边上的流量和残余容量之间有什么区别?
边上的流量表示沿该边传输的物料量,而残余容量是可用的剩余容量。残余容量随着流量的增加而减小,反向边则跟踪撤销流量的能力。
相关方法
参考文献
Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.
打开 DOI 文献已复制。Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
ISBN:978-0-262-03384-8已复制。