Ford–Fulkerson

释义 Definition

Ford–Fulkerson（福特–富尔克森算法）：一种用于求解网络最大流（maximum flow）问题的增广路算法框架。它通过反复在残量网络中寻找从源点到汇点的增广路径并增加流量，直到无法继续增广为止。（常见变体：用 BFS 选增广路的 Edmonds–Karp 算法。）

发音 Pronunciation (IPA)

/ˌfɔːrd fʊlˈkɜːrsən/

例句 Examples

We used Ford–Fulkerson to find the maximum flow in the network.
我们用福特–富尔克森算法来求这个网络的最大流。

In practice, Ford–Fulkerson can be slow if the augmenting paths are chosen poorly, so many implementations prefer Edmonds–Karp for its predictable performance.
在实际应用中，如果增广路选择不当，福特–富尔克森可能会很慢，因此很多实现更偏好 Edmonds–Karp，以获得更可预测的性能。

词源 Etymology

该名称来自两位研究者 L. R. Ford Jr. 与 D. R. Fulkerson。他们在网络流理论中提出并系统化了用“增广路 + 残量网络”逐步改进流量的思想，后来这套方法被统称为 Ford–Fulkerson。

相关词 Related Words

• Algorithm
• Augmenting Path
• Capacity
• Edmonds–Karp
• Flow Network
• Max Flow
• Min Cut
• Residual Graph

文学与经典出处 Literary Works

• Ford & Fulkerson，《Flows in Networks》（1962）：网络流理论的经典专著，系统讨论最大流与相关方法。
• Cormen, Leiserson, Rivest, Stein，《Introduction to Algorithms（CLRS）*》：在“最大流”章节中讲解 Ford–Fulkerson 方法及 Edmonds–Karp 等变体。
• Ahuja, Magnanti, Orlin，《Network Flows: Theory, Algorithms, and Applications》：网络流领域权威教材，包含最大流算法与工程实现讨论。