问题标签 [edmonds-karp]

Edmonds-Karp 算法说，每次增加最短路径时，源 s 和汇 t 之间的最短距离单调增加。在这个假设下，源 s 和汇 t 之间的距离不会超过 |V|。- 1. 我认为这意味着在 |V| 之后源 S 和接收器 T 之间将不再有路径。- 1个增强。如果这是真的，那么找到最大流量的复杂度将是 (|V| - 1) * E。

我知道我错误地假设了上述内容。但无法理解它是什么。谁能帮我 ？

我有一个集合，我需要在这个集合中生成两个元素对。作业都是加权的。匹配应该是受限的或完美的，取决于结果。我想，我需要在一般图表中进行加权匹配，据我所知，Edmonds 的算法是正确的地址。那正确吗？

我已经实现了 Kuhn-Munkres 算法，但我很晚才意识到这仅适用于二分图。是否有一种（简单的）方法可以将 Kuhn-Munkres 算法调整为 Edmond 的？否则我会选择爱德蒙算法。

我尝试在堆栈溢出中查找我的问题的答案。我找到了这些答案，但他们的解决方案并不真正适用于我的情况，因为我有非定向边缘。我无法创建一个新的顶点，边在 Vin 处进入，边在 Vout 处退出，因为在特定方向上没有“进入”或“退出”。

Edmonds-Karp 算法，用于具有具有流量的节点的图

（我找不到第二个堆栈问题，但答案相同）

最初的问题

我的问题是我有一个图，其中节点具有容量，所有边都是双向的，我需要找到所有路径，使我能够最大化 N 个元素在图中的流动。

基本上，它是一个 lem-in，房间容量为 1 和无限容量的双向边缘。

想象一个迷宫，你可以在隧道里容纳尽可能多的人，但每个房间只有一个人。他们可以在一个回合内从一个房间移动到另一个房间。我怎样才能做到这一点，以便人们从迷宫的开始到结束的所有方式，而不会有两个人在同一个房间里。

Edmonds-Karp 的实现

我已经设法使用邻接矩阵（它是一个使用位检查是否存在连接的整数的一维数组）实现了 Edmonds-Karp（可能非常糟糕）。

我有 3 个函数，一个运行算法本身的函数（我正在稍微简化代码，例如删除对 malloc、frees 等的保护……以便算法看起来更好）：

1. 主算法循环

这是主循环。我试图找到一条增广路径。如果我不这样做，这意味着最终房间的（接收器）父级将是初始值（-1）。否则我应用路径，打印路径并继续。

2. 找到增广路径

然后有一个函数可以找到增广路径。我只是使用带有队列的 BFS，弹出父级然后检查所有子级。如果一个孩子有一个前向连接并且仍然有容量，我将它添加到路径中，将其标记为已访问并将其推送到队列中。如果一个孩子有一个反向连接并流过它，我将它添加到路径中，将其标记为已访问并将其推送到队列中。

3. 应用增广路径

应用增广路径的函数非常简单，在我的例子中，所有边的容量都是 1。我们只是从终点（sink）返回，直到我们使用路径中保存的 ID 到达起点（点击）。对于每个房间，我们填充了从父母到孩子的容量和从孩子到父母的空闲容量。

我在以下情况下添加了一张支票：

if (!visited[child_id] && !map->rooms[child_id]->visited)

此检查!map->rooms[child_id]->visited)是我在从找到的路径构建方式时添加的已访问标志。它使我可以避免在某些情况下多次占用同一个房间。

如果我有多个边缘进入，在 Edmond-Karps 中，流量将受到边缘的限制。这意味着如果我有 4 条边到一个节点，我可以有 2 个元素进入，只要我有 2 条其他边让元素出去。这种检查避免了这种情况。

但是，这是我的主要问题，通过这样做，我阻止了一些可能通过迷宫的路径。

下面的图片将向您展示问题所在。没有我的额外检查，Edmonds-Karp 运行良好，但使用边缘来找到最佳流程：

这是我添加支票以避免两次使用同一个房间时的解决方案：

这是我想找到的：

有没有办法修改我的 Edmonds-Karp 实现以获得我想要的？如果没有，我可以使用其他算法吗？

非常感谢大家的耐心等待！

PS：我没有足够的声誉，无法嵌入图片:'(

福特富尔克森复杂性是O(FE)，但埃德蒙卡普斯是O(VE^2)。这是基于每条边只能达到临界O(V)次数的前提，这适用于所有边，所以我们有O(VE)边可能达到临界的次数，即可以找到增广路径的次数。这是有道理的，因为我们可以O(V)多次使用 1 条边，然后因为我们需要对图中的所有其他边都这样做，所以我们有O(VE)时间需要找到增广路径。然后是BFStake O(E)，所以我们得到了最终的 edmonds karp 复杂度。

但问题是：O(VE)关于增广路径数量的论点如此笼统，那么为什么不能将这种分析应用于福特富尔克森呢？似乎在不公平的基础上比较了两种算法的复杂性。edmonds karp 算法的优势是什么？

另外，为什么当我们在 edmonds karp 中使用 BFS 方法时，我们可以保证找到最短路径？有一个简短的证明吗？

我在 python 中使用了一个简单的 heapq，并在其上实现了lt函数的自定义元素。

然后我在另一个名为 P 的数组中保留一堆这些元素：

问题是当我堆放一个元素时，我希望它是我数组中的最小元素，对吗？但是这个断言在这里失败了

有人可以用一个例子向我解释 Borradaile-Klein 的最大流量算法是如何工作的吗？ http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.6392&rep=rep1&type=pdf

有很多 Ford-Fulkerson 的示例（https://www.youtube.com/watch?v=Tl90tNtKvxs），但我没有找到 Borradaile-Klein 算法的示例。

谢谢你。

我正在尝试学习 Java 上的 Max-Flow 算法。当我研究时，我发现了用于可视化和算法的 Jung 库，它对我很有用。我可以计算最大流量，但看不到每条边的计算流量。我想像这个例子一样在可视化中将流写入边缘： 在此处输入图像描述

代码：

我查看了文档（http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/flows/EdmondsKarpMaxFlow.html）。当我使用 getFlowGraph() 时，我只能获得边缘的容量。它没有显示流量。我无法获得流量。有什么办法吗？谢谢。

（来源：http ://www.groto-networking.com/JUNG/BasicDirectedGraph.java ）

我正在尝试使用 JUNG 的 EdmondsKarpMaxFlow 对象来查找有向图中所有节点对之间的最大流量。我创建了一个简单的有向图，并在每个节点组合上运行它，没有错误。这是供参考的工作示例： https ://pastebin.com/TLsEduxZ

但是，当我在更复杂的图形上调用相同的“edkAlg.evaluate()”代码时，循环每次都会在某个边/迭代处停止。

我使用顶点和边的自定义定义，它们的行为与预期的一样，但只是比普通示例具有更多的属性。该代码发现 v1 和 v2 之间的最大流量在前 201 次迭代之前非常好，但每次都卡在“.evaluate()”中（它每次都使用相同的对顺序，所以它总是卡在 problemNode123 ->问题Node456）。不太确定我哪里出错了，网上也没有太多帮助，所以任何指针都非常感谢！

我最近试图解决spoj上的最大流量问题。我在这里看到了最大流量的算法，所以我应用了它，但没有得到所需的答案。原因是我在我的实现中减少了边缘朝向接收器的容量，最终它达到零并且它不考虑反向容量（许多人在网上声称添加两条边，一条向前，一条向后代替一条无向边） . 你能帮我解决这个问题，或者告诉我如何使用 Edmonds-Karp 算法解决问题。

Boost 提供了三种不同的算法来查找有向图中的最大流量：boykov_kolmogorov、edmonds_karp和push_relabel。它们都有命名和非命名参数版本。他们使用的参数集也非常相似。尽管如此，使用相同的参数，这些算法中的一些可以编译，而有些则不能。

push_relabel与命名和非命名版本都可以很好地编译：

boykov_kolmogorov使用非命名版本编译：

但命名版本失败：

/celibs/boost_1_73_0/boost/graph/detail/adjacency_list.hpp:2768:17：错误：形成对 void 的引用

edmonds_karp失败，命名和非命名版本都出现相同的错误：

/celibs/boost_1_73_0/boost/concept_check.hpp:147:9：错误：使用已删除的功能

完整示例在这里：https ://godbolt.org/z/dvjfec

我是否以不正确的方式传递参数？如何正确传递它们？

谢谢！