问题标签 [ford-fulkerson]

我有一个图 G，它是一个有向且强连通的图，我被要求找到所有顶点对的最小割，这意味着图中的每一对 S 和 T。这应该在 O(m ² × n ² ) 时间内完成。

我想出的最好的方法是将所有顶点视为 S，并且对于每个 S，将所有其他顶点视为 T，并且对每个顶点运行 Ford-Fulkerson 算法，然后找到最小割。但如果我没记错的话，这个算法的复杂度是 O(m ² × n ² × C)。

我怎样才能在 O(m ² × n ² ) 时间内完成这项任务？甚至可能吗？

我正在学习 Ford Fulkerson 算法，我对后向边缘的目的以及它们如何帮助我们达到最大流量感到困惑。我看过几个不同的视频并阅读了一些关于算法的文档，但没有任何点击。也许这里有人可以用对我来说有意义的方式来表达它！

问题是：

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

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

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

我正在尝试实现 Ford-Fulkerson 的 java 版本。我使用了wikipedia中的 python 实现作为基础：

这是我的java实现：

问题是 java 算法输出 7，而不是测试用例中给出的示例的正确 23。代码运行时没有错误。在调试算法时，我看不到任何不当行为。我不确定它是怎么出错的。

我的问题是，谁能帮助我理解它是如何以及为什么出错的？

如果它有助于此 pdf 中提供示例图的可视化表示： http ://web.stanford.edu/class/cs97si/08-network-flow-problems.pdf

基于这篇很棒的文章http://www.geeksforgeeks.org/maximum-bipartite-matching/ ，我有一个 Ford Fulkerson 算法的工作 php 实现

目前，控制算法的矩阵可以在其单元格中具有 1 或 0 的值，以表示每个员工在该职位上工作的可能性。我想为算法增加容量，基本上在矩阵中放置更高的值，如 2、3 等，以表达选择员工而不是另一个员工的偏好。

您对如何编辑算法以增加容量有什么建议吗？

这是算法代码：

这就是我创建矩阵的方式：

非常感谢，马可

嘿，所以我有一个图，例如 3 条边进入一个节点，3 条边出来，但是如果一个特定的输入边有容量，我只需要激活输出边。例如，如果我们有：

A -> N

B -> N

C -> N

N -> N'

N' -> A'

N' -> B'

N' -> C'

如果 A 有流量，我只想流过 A'，如果 B 有流量等，我只想流过 B'。

基本上它是边缘 A、B、C 的容量限制器，我最初无法限制它们的容量。

假设这种情况发生多次，我如何将此约束添加到最大流量并解决给定图的最大流量图问题？

编辑：我最终也不能限制它们的容量，因为稍后会在图中使用 A'、B' 和 C'，所以我不能将 N 和 N' 移动到最后并在以后强制组合容量减少。

我试图弄清楚在这种情况下我应该如何使用福特富尔克森算法这种情况有点像数独。我们有一个a包含整数值的矩阵。每行的最后一列和每列的最后一行，包含整行/列的总和。

例子：

这件事是，矩阵中的值并不总是正确的。总和的值并不总是正确的，例如：

有一个矩阵b包含一个单元格可以满足给定总和的最大差异。例如

例如，对于 的值a[0][0]，即 1，最大差异是 的值b[0][0]，即 1，因此a[0][0]可以将 at 的值更改为最大 0 或 2（以及介于两者之间的所有数字，但对于此示例，我们只有2 个选项）。

我的问题是：给定一个矩阵a（给定总和的值无效）和一个b具有最大差异的矩阵，可用于满足所需的总和，我如何确定在给定的最大差异下是否有可能，我该怎么做得到这样一个矩阵的有效结果（如果存在的话）。

我目前的方法（不起作用）：

• 制作行和列的二分图，因此每行和列都有一个源、一个接收器和一个节点。
• 然后将每一行连接到每一列。
• 然后将源连接到每一行。
• 然后将每列连接到水槽。
• 将从源到每个行节点的边的容量设置为 Math.Abs​​（当前数字总和a- 给定数字总和a（对于该行））。
• 从每个列节点到接收器的边缘相同（但这次是列总和）。
• 将行到列的节点之间的容量相应地设置b为每个单元格的给定最大差异。
• 使用 Ford Fulkerson 确定最大流量。

我不知道我应该如何使用我的算法结果来确定矩阵的正确值a以满足每一行和每一列的给定总和。

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

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

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

我正在尝试学习 Ford-Fulkerson 方法。我已经制作了一个练习示例，在某些时候我无法继续增加流量，但我知道流量可能会更高。

首先，我增加了路径s -> 1 -> 2 -> t。现在我找不到任何增加流量的途径。我知道如果我a -> 1 -> 5 -> 6 -> t先采取路径，那么我可以增加路径s -> 3 -> 4 -> 2 -> t，但如果我必须实现它，我不知道该怎么做。

我究竟做错了什么？

我正在阅读 Robert Sedgewick 编写的 Algorithms 一书中的 Ford-Fulkerson maxflow 算法。这里作者提到如下

对于具有 V 个顶点和 E 个边的流网络，Ford-Fulkerson maxflow 算法的最短增广路径实现所需的增广路径数最多为 EV /2。

证明草图：每条增广路径都有一条关键边——一条从残差网络中删除的边，因为它对应于一条被填充到容量的前向边或一条被清空的后向边。每当一条边是关键边时，通过它的增广路径的长度必须增加 2。由于增广路径的长度最多为 V，因此每条边最多可以在 V/2 增广路径上，并且总增广路径最多为 EV/2。

我对上述文字的问题是

1. 我们如何说如果增广路径长度最多为 V，则每条边最多可以在 V/2 增广路径中？

如果可能的话，要求用简单的例子来解释上面的内容。