algorithm - Edmonds-Karp 算法的复杂性

Question

Edmonds-Karp 算法说，每次增加最短路径时，源 s 和汇 t 之间的最短距离单调增加。在这个假设下，源 s 和汇 t 之间的距离不会超过 |V|。- 1. 我认为这意味着在 |V| 之后源 S 和接收器 T 之间将不再有路径。- 1个增强。如果这是真的，那么找到最大流量的复杂度将是 (|V| - 1) * E。

我知道我错误地假设了上述内容。但无法理解它是什么。谁能帮我 ？

Answer 1

在我的《算法简介》（可能是早期版本）中，他们在引理 27.8 中说“单调增加”，但他们真正证明的是，如果它减少，就会出现矛盾。他们在定理 27.9 中提到这个引理的地方，他们只是说因为 DELTAf(x,v) <= DELTAf'(S,v) 所以看起来当他们说单调增加时，他们实际上是指“不减少”或“增加或保持不变”相同”。如果它可以保持不变，则不能像以前那样使用它来限制迭代次数。