algorithm - 为什么福特-富尔克森如此普遍？

Question

在查看最大流量解决方案时，福特-富尔克森似乎无处不在，因为它是大多数人用来解决这个问题的算法。然而，还有更多的算法可以解决这些问题，而且时间复杂度要好得多。那么为什么当时福特-富尔克森仍然如此广泛使用呢？

Answer 1

Ford-Fulkerson 是最简单的算法，它体现了一个关键思想，即当且仅当它没有增广路径时，流才是最大的。这使它对教学有用。

由于 F-F 没有指定如何找到增广路径，因此它更像是一个框架而不是算法。Edmonds-Karp 是 F-F 的一个实例，它限制了必须找到的增广路径的数量。Dinic 的算法在 Edmonds-Karp 的基础上进行了改进，保留了一种数据结构，使其能够更有效地找到增广路径。（有点偏僻，由于Borradaile 和 Klein ，平面网络中 st 流的 O(n log n) 时间算法也是 F-F 实例化。）

push-relabel 算法将 Dinic 算法背后的思想更进一步，但它们在使用预流而不是流时打破了 F-F 模式（预流允许更多流进入顶点而不是叶，反之亦然）。从历史上看，他们遵循了 Dinic 的算法，并作为对 Dinic 的反应更直观。

该列表中的其他算法很复杂，不适合本科教学，这解释了缺乏教程材料的原因。