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 增广法的分析与改进版本：规定每次选择“最短（按边数）增广路”，从而给出明确的多项式时间界。

相关词 Related Words

• Augmenting
• Bfs
• Capacity
• Dinic
• Flow
• Ford-Fulkerson
• Max-Flow
• Network
• Residual

文学与著作中的出现 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）的广泛引用与教学化传播。