科门“算法导论”第三版-埃德蒙兹-卡普斯-算法-引理26.7

Question

由于我认为我们中的许多人没有Cormen教授等人的“算法导论”的相同版本，所以我将在下面写这个引理(和我的问题)。

Edmonds-Karp算法

引理26.7 (在第3版；在第2版，可能是引理26.8)：如果Edmonds-Karp算法是在源s和接收器t的流网络G=(V，E)上运行的，那么对于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的最短路径，使得(u，v)在Ef’和

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

由于我们选择v的方式，我们知道顶点u与索鲁斯之间的距离并没有减少。

df'(s，u) >= df(s，u)(26.13)

..。

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

由于我们选择v的方式，我们知道顶点u与索鲁斯的距离并没有减少，即df'(s，u) >= df(s，u)。(26.13)

我们选择v的方式如何影响“顶点u到s的距离没有减少”的性质？如何导出方程(26.13)。

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

谢谢你们的帮助。

Answer 1

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

在某些历史上，请注意福特-富尔克森算法是第一位的。Fulkerson简单地选择从源到接收器的任意路径，将流量添加到当前容量，然后相应地增加剩余图。由于所选择的路径可能是任何假设，在某些情况下，这种方法需要“永远”(从比喻和字面上说，如果允许边缘权重是不合理的)实际终止。

埃德蒙斯-卡普做的事情和福特-富尔克森一样，只是选择了“最短”路径，这可以通过广度优先搜索(BFS)找到。

BFS保证了遍历顶点之间的某种(部分)排序。例如，考虑下面的图:a -> B -> C，BFS保证B在C之前被遍历(您应该能够用更复杂的图形概括这个论点，这是我留给您的练习)。对于这个帖子的其余部分，让"n“表示BFS中到达目标节点所需的级别数。所以，如果我们在上面的例子中搜索节点C，n= 2。

埃德蒙斯-卡普的行为类似福特-富尔克森，但它保证了最短的路径首先选择。当Edmonds更新残差图时，我们知道实际上只有等于或小于n的节点被遍历。类似地，在残差图中，只有前n层的节点之间的边可能被更新。

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

希望这能有所帮助，并至少给出一些见解。

Answer 2

我也不太明白。但我认为“我们如何选择v”在这里意味着流增强只会使从s到v的路径变短，另一方面，v是从s到s的路径因增大而变短的第一个节点，因此节点u与s的距离不会变短。