1

因为我认为我们中的许多人没有相同版本的 Cormen 等人的“算法简介”，所以我将在下面写引理（和我的问题）。

Edmonds-Karp 算法

引理 26.7（第 3 版；第 2 版可能是引理 26.8）：如果 Edmonds-Karp 算法在源 s 和汇 t 的流网络 G=(V,E) 上运行，则对于 V 中的所有顶点 v{ s,t}，残差网络 Gf 中的最短路径距离 df(s,v) 随着每次流量增强而单调增加

证明：首先，假设对于V{s,t}中的某个顶点v，存在一个流增广导致s到v的最短路径距离减小，那么我们将推导出一个矛盾。令 f 是第一次增强之前的流，它减少了一些最短路径距离，让 f' 是紧随其后的流。令 v 为具有最小 df'(s,v) 的顶点，其距离因增强而减小，因此 df'(s,v) < df(s,v)。令 p = s ~~> u -> u 是 Gf' 中从 s 到 v 的最短路径，因此 Ef' 中的 (u,v) 和

df'(s,u) = df'(s,v) - 1. (26.12)

由于我们如何选择 v，我们知道顶点 u 到源 s 的距离没有减小，即

df'(s,u) >= df(s,u)。(26.13)

...

我的问题是：我不太明白这句话

"因为我们选择 v 的方式，我们知道顶点 u 到源 s 的距离没有减小，即 df'(s,u) >= df(s,u). (26.13) "

我们选择 v 的方式如何影响“顶点 u 到 s 的距离没有减小”的性质？我怎样才能推导出方程（26.13）。

我们知道，u 是路径 (s,v) 上的一个顶点，并且 (u,v) 也是 (s,v) 的一部分。为什么 (s,u) 也不能减少？

谢谢大家的帮助。

4

2 回答 2

1

我的答案可能会被抽出，但希望它有助于全面理解。

对于一些历史，请注意 Ford-Fulkerson 算法首先出现。Ford-Fulkerson 简单地选择从源到汇的任何路径，将流量添加到当前容量，然后相应地增加残差图。由于假设选择的路径可以是任何东西，因此在某些情况下，这种方法需要“永远”（形象地和字面地说，如果允许边缘权重是非理性的）实际终止。

Edmonds-Karp 与 Ford-Fulkerson 做同样的事情，只是它选择“最短”​​路径，可以通过广度优先搜索 (BFS) 找到。

BFS 保证遍历的顶点之间的特定（部分）排序。例如，考虑下面的图：A -> B -> C，BFS 保证 B 将在 C 之前被遍历。（你应该能够用更复杂的图来概括这个论点，我留给你一个练习。）对于这篇文章的其余部分，让“n”表示在 BFS 中到达目标节点所需的级别数。因此，如果我们在上面的示例中搜索节点 C，则 n = 2。

Edmonds-Karp 的行为类似于 Ford-Fulkerson，只是它保证首先选择最短路径。当 Edmonds-Karp 更新残差图时，我们知道实际上只有级别等于或小于 n 的节点被遍历。类似地，只有前 n 个级别的节点之间的边可能在残差图中被更新。

我很确定“我们如何选择 v”反映了 BFS 保证的顺序，因为添加的残差边缘必然会在任何选定路径的相反方向上流动。如果残差边要创建一条更短的路径，那么首先就有可能找到比 n 更短的路径，因为只有在找到到目标节点的路径时才会创建残差边，并且 BFS 保证已经找到了最短的这种路径。

希望这会有所帮助，至少可以提供一些见解。

于 2015-01-29T19:58:43.560 回答
0

我也不是很明白。但是我认为这里的“我们如何选择v”意味着流增强只会导致从s到v的路径变短，换句话说，v是第一个因为增强而从s的路径变短的节点，因此节点u 与 s 的距离不会变短。

于 2014-11-07T03:51:34.377 回答