Edmonds-Karp 算法

Edmonds-Karp 算法是求解网络最大流问题的经典算法,由 Jack Edmonds 与 Richard Karp 于 1972 年提出。它是 Ford-Fulkerson 方法的一个特化:每次都用广度优先搜索(BFS)在残量网络中寻找一条最短的增广路径,从而把复杂度约束为多项式级,与边容量的具体数值无关。

概述

最大流问题要在一个带容量的有向网络中,从源点向汇点尽可能多地输送流量。Ford-Fulkerson 方法的框架是反复寻找增广路径并沿其增流,但若增广路选择不当,朴素实现的迭代次数可能与容量数值相关而变得很慢。Edmonds-Karp 通过固定用 BFS 找最短增广路,消除了这一隐患。

核心原理

算法在残量网络上反复执行:用广度优先搜索从源点找一条到汇点的、经过边数最少的增广路径;沿该路径找出瓶颈容量并增流,同时更新正向和反向的残量;直到再也找不到增广路径为止,此时的流即为最大流。

• 选择最短增广路:BFS 保证每次增广的路径边数最少。
• 复杂度保证:可以证明增广轮数不超过顶点数乘边数量级,故总复杂度为顶点数乘边数平方,与容量大小无关。
• 正确性:算法终止时不存在增广路,由最大流最小割定理可知此时流量已达最大。

应用场景

Edmonds-Karp 算法用于求解各类可归约为最大流的问题,如二分图最大匹配、项目选择、网络可靠性分析等。虽然在稠密图上它常被更快的 Dinic 算法取代,但其思路清晰,是理解最大流理论和证明多项式复杂度的重要范例。

常见问题

问:Edmonds-Karp 和 Ford-Fulkerson 是什么关系?答:Ford-Fulkerson 是一类方法的统称,并未规定如何找增广路;Edmonds-Karp 是其具体实现,明确规定用 BFS 找最短增广路,从而获得多项式复杂度保证。

问:它和 Dinic 算法哪个快?答:Dinic 算法通常更快。Dinic 用分层图和阻塞流一次处理多条增广路,复杂度更优,Edmonds-Karp 胜在实现简单、易于理解和证明。