Skip to content
返回搜索结果

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 等专用算法高效
  • 对增广路径的选择顺序敏感

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 基于增广路径的简单直观方法
  • 当容量为有理数或整数时,保证得到最优解
  • 对于具有小整数容量的网络效率高
  • 构成了理解最大流最小割对偶性的理论基础
  • 可用于有向图和无向图

应用

  • 网络路由:在通信网络中最大化从源点到目的地的吞吐量
  • 交通网络:在考虑道路和铁路约束的情况下,确定城市之间的最大货物容量
  • 二分图匹配:通过构建流网络在二分图中找到最大匹配
  • 图像分割:使用最大流算法将图像分割为前景和背景
  • 航空公司调度:优化飞机路线以最大化通过枢纽辐射网络的乘客流量
  • 蛋白质分析:计算生物网络中的最大流以理解相互作用通路

使用方式

使用方式

1

初始化残余图,使边容量等于原始边容量,所有边的流量为零。

2

在残余图中,使用深度优先搜索或广度优先搜索寻找从源点到汇点的增广路径,计算路径上的最小容量,并将此流量加到路径上的所有边,同时减小它们的残余容量。

3

重复增广,直到残余图中不存在增广路径;累积的总流量即为最大流。

常见陷阱

  • 选择糟糕的增广路径,导致收敛缓慢或结果不正确
  • 未能正确更新残余容量或添加反向边来撤销流量
  • 在需要精确算术以保证正确性的情况下,使用了整数除法或浮点算术

常见问题

什么是最大流最小割定理?

该定理指出,从源点到汇点的最大流等于分隔源点和汇点的任何割的最小容量。这提供了理论洞察和流算法的验证方法。

为什么该算法有时收敛缓慢?

在不幸的路径选择下,即使可以进行更大的增广,算法也可能每次迭代只增广一个单位的流量。使用广度优先搜索(Edmonds-Karp)可确保多项式时间收敛。

该算法如何处理无向边?

将每条无向边替换为两条方向相反的有向边,两者具有相同的容量。然后,算法在有向网络中寻找流量。

边上的流量和残余容量之间有什么区别?

边上的流量表示沿该边传输的物料量,而残余容量是可用的剩余容量。残余容量随着流量的增加而减小,反向边则跟踪撤销流量的能力。

相关方法

参考文献

  1. Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.

    打开 DOI 文献
    已复制。
  2. 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
    已复制。