Edmonds-Karp

释义 Definition

Edmonds–Karp（埃德蒙兹–卡普算法）：一种用于求解网络最大流（maximum flow）的经典算法，是 Ford–Fulkerson 方法的特例；它在每次增广时用 BFS 在残量网络中寻找边数最少的增广路，从而保证多项式时间复杂度（常见记为 **O(V·E²)**）。

发音 Pronunciation (IPA)

/ˈɛdməndz kɑːrp/

例句 Examples

The Edmonds-Karp algorithm finds a maximum flow using BFS.
Edmonds-Karp 算法使用 BFS 来寻找最大流。

In dense graphs, Edmonds-Karp is often slower than Dinic’s algorithm, but it is easier to implement and analyze.
在稠密图中，Edmonds-Karp 往往比 Dinic 算法更慢，但它更容易实现和分析。

词源 Etymology

名称来自两位计算机科学家 Jack Edmonds 与 Richard M. Karp。该算法通常指 Karp 在 1972 年对 Ford–Fulkerson 增广法的分析与改进版本：规定每次选择“最短（按边数）增广路”，从而给出明确的多项式时间界。

文学与著作中的出现 Literary Works

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein：《Introduction to Algorithms》（《算法导论》）— 最大流章节常介绍 Edmonds–Karp 作为基准算法之一。
Jon Kleinberg, Éva Tardos：《Algorithm Design》— 网络流部分讨论 Edmonds–Karp 与其他最大流算法的对比。
R. K. Ahuja, T. L. Magnanti, J. B. Orlin：《Network Flows: Theory, Algorithms, and Applications》— 将 Edmonds–Karp 作为经典最大流方法纳入体系化讲解。
Richard M. Karp（1972）：“Reducibility Among Combinatorial Problems” — 在相关讨论中促成了对该 BFS 增广版本（常称 Edmonds–Karp）的广泛引用与教学化传播。