问题标签 [edmonds-karp]

考虑我们有一个网络流量，并且使用 Edmond-Karp 算法，我们已经有了网络上的最大流量。现在，如果我们向网络添加任意边（具有一定容量），那么更新最大流量的最佳方法是什么？我正在考虑更新关于新边缘的残差网络并再次寻找增强路径，直到我们找到新的最大流量，但我不确定它是否有效或者它是否是最好的方法！

为什么每次都选择最短增广路径而不是任意增广路径会使 Edmond Karps 算法比 Ford-Fulkerson 更快

我正在尝试在 Boost-graph 库的算法中使用具有捆绑属性的命名参数。edmonds_karp_max_flow

为了说明我的问题，我采用了现有的edmonds-karp 示例并将内部属性转换为捆绑属性（我将我的属性称为edge_t和node_t），并将命名参数转换为非命名参数。

这是编译良好的非命名参数版本：

这是不编译并触发大量模板错误的命名参数版本：

完整edmonds-karp-eg_modified.cpp来源：

以下是返回的错误：http: //pastebin.com/Vra8ZWHG。

它适用于非命名参数......但不适用于命名参数。

更新：有人似乎有完全相同的问题：svn.boost.org/trac/boost/ticket/8791。他使用Boost 1.50而不是修复它1.55。

• 升压图版本：1.58.0
• 编译器：g++ 5.0

问题是：

对于 (a) 似乎不正确，我们可以找到一个流量在不饱和的情况下增长的示例。

对于（b）这似乎是正确的，但我不知道如何证明它。也许是因为最小切割最大流量定理，它在最小切割上，所以它必须增长。

对于 (c) 它似乎是错误的。流量增加是因为 e 发生了变化，但 e 可能没有正好增长 5。

我正在尝试学习在 java 中实现 Ford-Fulkersons 算法并在互联网上找到了一些帮助，但我被困在这段代码中

由于评论，我有点理解它的工作原理，但不完全确定为什么需要它。为什么需要减法？

资料来源：http ://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/

当 Edmonds-Karp 算法说沿路径 p 增加流量 f 时，增加流量实际上意味着什么？这是否意味着沿着路径发送流量？

那么如果 2 条最短的增广路径长度为 2，那么二级过滤器是什么？

据我了解，Edmonds-Karp 选择最短路径，即边数最少的路径。

但是，这两条路径的长度都是 2。那么该算法是否会扩展并说“选择具有最大/最小流量的路径”？

我试图在 C++ 中实现Edmonds-Karp以获得最大流量，但我的编写方式略有不同：

1. 我没有遍历残差图中的所有边，而是使用邻接表仅遍历原始图中存在的边。
2. 用最小流量更新残差图时，我没有更新任何后边。

有趣的是，当我运行我的代码时，它给了我正确的结果。因此，我查看了Wikipedia 的示例，它专门展示了如何使用后端。当我将此图提供给我的代码时，我再次得到了正确答案。我还检查了结果流矩阵，它与维基百科的相同。

有人可以解释为什么我们必须添加和更新 back-edges，并可能举一个它们很关键的例子吗？

这是我编写的代码（更新为包括后边缘）：

我正在实现一个程序来解决匹配问题，方法是使用从匹配问题到最大流量问题的减少，我决心使用 Edmond-Karp 算法来解决这个问题。

我已经查看并从不同的伪代码中获取印象，这些伪代码告诉如何使用 Edmond-Karp 算法执行解决最大流量问题的过程，并通过混合这些印象，我生成了一个适用于许多小型基本图的实现. 但是由于某种原因，该实现对更大的图给出了错误的答案，例如具有 100 条边的 50 个节点，甚至比此类图更大。因此，给出一个输入输出场景示例对于突出整个问题并没有太大帮助（如果您坚持，我可以按照您的意愿发布这样的输入输出场景）。当我说“错误答案”时，实现实际上并没有给出最大匹配（或最大流量值）给定要解决的图形。

在下面，您可以拥有在我的实现中使用的所有相关类，即在 MaxFlowSolver 类中（方法 solveFlowProblem(...) 是使用整个 Edmond-Karp 算法的方法）：

MaxFlowSolver

图形

边缘

我主要遵循维基百科对使用邻接节点的 Edmond-Karp 算法的描述，但也有一些来自其他来源，但没有那么多。维基百科上的算法链接如下：

https://en.wikipedia.org/wiki/Edmonds –Karp_algorithm#Pseudocode

在我的实现中是否有某个地方我错误地解释了维基百科上的伪代码，或者它是否更具体地与我的 Java 代码有关？我几乎整天都在使用这个程序，但没有弄清楚是什么导致了某些图形的程序没有输出某些图形的最大匹配（或最大流量）的问题。

我能从你那里得到的所有帮助将不胜感激。

谢谢大家！

最大流问题通常通过 edmond-karp 算法来解决，该算法构建残差图，并使用 BFS 寻找增广路径。

但通常最大流量问题是为加权图定义的。对于未加权的图，我们可以简单地将每条边的权重视为1，但我想知道是否有更简单的算法来解决未加权的版本。