问题标签 [ford-fulkerson]

我正在做课堂作业，但遇到了一个我无法弄清楚的问题。我正在使用 BFS 实现 Ford-Fulkerson 算法来查找最大流量。但是在尝试将我的剩余容量矩阵设置为给定容量时，我遇到了分段错误。在我们收到的测试代码中，我可以看到原始容量矩阵是通过其地址按值传递的，但我有一种感觉，在我的代码中我并没有像我想象的那样与它交互？这让我相信我可能会在其他地方再次出现同样的问题。我使用 gdb 并看到我在嵌套 for 循环中的这一行上遇到了分段错误：

但是，我尝试过的任何东西都没有为我工作，所以我很难过。

这是提供给我们的测试代码，以备不时之需：

你能帮我解决以下问题吗？：

假设我们有一个算法来解决每个节点的出度最多为 2 的流网络中的最大流量问题。我需要展示如何使用该算法来解决任何网络中的最大流量问题。

如果这是重复，请把我重定向到相关答案。

谢谢你们

在以下情况下，重新计算图中最大流量的最有效方法是什么：

• 我们将一侧的流量增加一
• 我们将一侧的流量减少一

在第一种情况下，是否足以运行一次福特-富克森算法的迭代？在第二种情况下，只有当边是一组最大流量的边的一部分时，我们才需要重新计算最大流量。运行一次 Ford-Fulkerson 迭代是否也足够？

如果对于给定的流网络，残差网络中有许多增强路径，我应该首先采取什么路径来找到瓶颈容量？

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

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

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

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

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

稍微重申一下这个问题：我们有一个流程图 G，它具有整数容量。我们能否找到一个最大流，其中至少有一个边 e，我们有 f(e) 等于一个非整数？

我第一次尝试这个时，我有点掩饰它，并认为这违反了完整性定理，因此它是错误的，但仔细阅读后发现它并没有违反任何规则。显然这是真的。

我一直在尝试绘制一个简单的示例来获得可视化，但我似乎无法提出任何建议。任何人都可以向我展示一个可以使用的示例流程图吗？

假设已经使用 Ford-Fulkerson 计算了 G 的最大流量，并且将具有单位容量的新边添加到 E。如何有效地更新最大流量。（t 不是必须更新的流的值，而是流本身。

假设 G 的最大流量已使用 Ford-Fulkerson 计算，但现在从 E 中删除了一条边。如何有效地更新最大流量。

这是我的 python 代码，用于在具有源 S 和接收器 D 的多接收器、多源图 (E) 上执行 Ford-Fulkerson 操作。将流过的最大值为 200 万。我使用虚拟源和虚拟接收器来解决这个问题。我知道我正确设置了虚拟源和接收器。因为如果我将 Geek 用于 Geek 的实现，我的代码就会通过，但我真的很想了解为什么我的代码不起作用。有人有建议吗？

我需要解释究竟什么是节点不相交的路径？以及如何确定有向图中两个节点 Source(s) 和 Sink(t) 之间的节点不相交路径的最大数量。任何人都可以用图形解释。