Edmonds-Karp算法的复杂性

Question

edmonds-karp算法说，源S和水槽之间的最短距离是每次最短的路径都会增加。随着源S和接收器T之间的这种假设距离，t的距离将不多。 - 1.我认为这意味着| V |之后的源s和接收器之间将不再有路径。 - 1增强。如果这是真的，那么查找最大流量的复杂性将为（| v | -1） * E.

我知道我错误地假设了上面的事情。但无法理解它是什么。谁能帮我？

Answer 1

在我的《算法简介》副本（可能是早期版本）中，他们在引理27.8中说"单调增加"，但他们真正证明的是，如果它减少了，就会有矛盾。他们在定理27.9中指的是此引理的地方，他们只是自从Deltaf（x，v）＆lt; = deltaf'（s，v）以来就说保持不变"。如果可以保持不变，则不能像您一样使用它来绑定迭代次数。