问题标签 [edmonds-karp]

我使用在 Edmonds–Karp 算法 wiki 页面中找到的伪代码实现了 Edmonds–Karp 算法：http ://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm

它工作得很好，但算法输出是最大流量值（最小切割值），我需要这个切割包含的边列表

我试图改变算法，但没有成功，你们能帮忙吗？

谢谢

如果所有路径的长度相同，如何选择Edmonds-Karp 算法的起始路径？在这种情况下，最大流量根据路径顺序决策而变化。

我正在为有向图实现此算法。但是这个图节点的有趣之处也有它们自己的流量能力。我认为，必须以特殊的方式处理原始问题的这种细微变化。因为，在原始的最大流问题中，从头到尾找到任何路径都可以（实际上，在 Edmonds-Karp 算法中，我们需要做 BFS，并选择到达最终节点的第一条路径）但是有了这个节点-容量扩展，我们需要更加小心“这条路径选择”的工作。我知道是因为，我实现了原始算法，发现自己的流量值比最大流量小，我怀疑这与节点容量限制有关。

我为此付出了很多努力，并提出了一些想法，例如通过添加自循环将初始图转换为对节点没有容量限制的图（向每个节点添加自循环并为每个节点找到包含此自循环的路径）路径上的节点）或添加权重取代初始节点容量约束的虚拟节点和边）但是，我不相信这些都是解决这个问题的好方法。

任何想法将不胜感激。

提前致谢。

我会实现Edmond Karp 算法，但它似乎不正确而且我没有得到正确的流程，请考虑以下图表和从 4 到 8 的流程：

算法运行如下：

先找4→1→8，再找4→5→8，再找4→1→6→8

而且我认为第三条路径是错误的，因为使用这条路径我们不能使用 6→8 的流（因为它使用过），实际上我们不能使用 4→5→6→8 的流。

事实上，如果我们选择 4→5→6→8，然后是 4→1→3→7→8，然后是 4→1→3→7→8，我们可以获得更好的流量（40）。

我从 wiki 示例代码中实现了算法。我认为我们不能使用任何有效的路径，实际上这种贪婪的选择是错误的。

我错了吗？

代码如下（c#中阈值为0，不影响算法）：

当唯一可用容量为 0 和 1 时，Edmonds Karp (BFS) 上限是多少？

我不明白容量只有 0 和 1 时的区别，我知道如果容量为 0 和 1，福特 Fulkerson 发现流量值为 0 或 1。这对我有帮助吗？

在我深入探讨这个问题之前，这里有一些我已经拥有的背景信息：

-我首先创建了一个基于美国城市的无向邻接矩阵图，边权重是计算距离（通过距离公式实现）。

-我还使用 prim 算法实现了最小生成树。

现在我需要实现我拥有的 Edmonds Karp 最大流量算法，但我对如何根据我拥有的数据创建容量图以实现以下代码中使用的算法感到困惑：

任何帮助将不胜感激，谢谢！

Ford-Fulkerson 和 Edmonds-Karp 等。人。从零流量开始并增加它，直到它不能再增加。在正容量的情况下；但是，保证初始零流量既是合法流量，又是满足容量约束的流量。

对于负容量，全零的流量分配将无法满足容量约束，因此无法将其扩充为最大流量。

我在互联网上读到有人建议，负容量的最大流量可以作为两个最大流量问题来解决，但一直无法弄清楚如何去做......

所以让我解释一下这个问题：

给你一张图表。你找到最大流量。但事实证明，边 e_i 的容量错误。它少了一个。不幸的是，流量在旧容量下已达到极限。

一旦您被告知 e_i 容量错误，请在线性时间内计算新的最大流量（根据边和顶点的数量）。

这是我的计划：（1）你不能只在边上将边 e_i 处的流减少一个，因为你必须违反某些约束：就像流在边上是守恒的。修复流程，以便您可以获得有效的流程。但是怎么做？

（2）有人给我提示：显示有效流=先前流-1.mmm会有所帮助...

帮助。

我正在尝试更详细地了解 Edmonds-Karp 算法，并且很想知道它使用什么算法来计算每次迭代从 s 到 t 的最短路径（最少边数）

因为我认为我们中的许多人没有相同版本的 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) 也不能减少？

谢谢大家的帮助。