Edmonds-Karp算法的复杂性

Question

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

我知道我错误地假设了上面的某些东西。但是不能理解它是什么。有人能帮我吗？

Answer 1

在我的算法导论(可能是早期版本)的副本中，他们在引理27.8中说“单调增加”，但他们真正证明的是，如果它减少了，就会有矛盾。当他们提到定理27.9中的这个引理时，他们只是说DELTAf(x，v) <= DELTAf'(S，v)，所以看起来当他们单调地说增加时，他们真正的意思是“不减少”或“增加或保持不变”。如果它可以保持不变，那么您就不能像以前那样使用它来绑定迭代次数。