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) so it looks like when they say increases monotonically they really mean "does not decrease" or "increases or remains the same". If it can remain the same, you cannot use it to bound the number of iterations as you have done.

Answer 2

Edmonds-Karp 算法使用增广路径的概念，每条新的最短路径都会增加源 s 和汇 t 之间的距离。但是，您的推理存在一些误解：

1. 路径限制：假设|V|之后不再存在路径- 1 增强不正确。实际上，增广路径的最大数量将为 O(VE)。这是因为，在每次迭代中，找到增广路径都需要对图进行广度优先搜索 (BFS)，其时间复杂度为 O(E)。 Edmonds-Karp算法的总体时间复杂度为O(VE^2)。这是从具有最多 |V| 得出的。 - 1 个增广乘以 O(E) BS 操作来找到每个增广路径。

为了进一步澄清，以下术语可分为以下几类：\

• 每个BFS寻找一条增广路径：由于BFS探索图中的所有边，因此其复杂度为O(E)，其中E是边的数量。
• 路径长度：增广路径的长度最多为|V| -1 就边缘而言。
• 增广路径数： O(VE)
• 总体来说： O(VE) * O(E) = O(VE^2)