问题标签 [ford-fulkerson]

给定一个无向图G = (V, E), u, v,w是 G 中的一些边。

描述一个算法来确定是否

“如果有一条从 u 到 w 的路径经过 v”

下面给出了一个使用 DFS 的简单算法：

对于上述算法，

• 时间复杂度：O(V+E)
• 空间复杂度：O(V)

但是我们可以降低时间复杂度吗？

所以我正在学习算法测试，但无法弄清楚这个问题的诀窍：

我需要展示一个带有流 f 的流网络的示例，在这种方式中，在残差网络中，s（源）和 t 之间存在一条容量大于 0 的路径，这使得流在不存在于原始流网络中。我需要解释如何增加原始网络中的流量。

所以如果这个边在原来的流网络中不存在，那意味着他的容量为0。我怎样才能让流变得更好呢？因为在残差中，只有在网络中“返回”的流。我想也许由于流程要倒流，我可以将 in 用于其他路径？

在查看最大流量解决方案时，福特-富尔克森似乎无处不在，因为它是大多数人用来解决这个问题的算法。然而，还有更多的算法可以解决这些问题，而且时间复杂度要好得多。那么为什么当时福特-富尔克森仍然如此广泛使用呢？

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

我正在尝试使用有向图确定一个有效的最大流量算法，其中给定n 个航班的列表（其中每个条目都有起始城市、结束城市、出发时间、到达时间和航班容量），将路由尽可能多的人从城市 A 开始并在城市 B 结束。我还希望能够返回一组可以乘坐的航班，以便尽可能多的人从城市 A 到达城市 B。我认为它可以只是 Ford-Fulkerson 算法或类似算法的实现，但我无法以有效的方式将此计划转换为最大流实例，特别是所述算法的伪代码看起来如何就像这样做之后。

我一直在研究这个问题的算法，但无法弄清楚。问题如下：

在与 X 球员的比赛中，每个球员都在赌 NBA 篮球比赛的结果。

猜对比赛结果的玩家得 3 分，猜对比赛的 MVP 得 1 分，猜错的都得 0 分。

该算法需要能够确定某个玩家是否无法达到该投注游戏中的第一名。

例如，假设联盟总共有 30 场比赛，那么玩家猜对的最高分是 (3+1)*30=120。

在下表中，您可以看到球员 X、Y 和 Z。球员 X 到目前为止猜对了 20 场比赛，因此他得了 80 分。玩家 Y 和 Z 分别得到 26 和 15 分，由于只剩下 10 场比赛，即使他们猜对了剩下的 10 场比赛，也不足以到达第一名。因此，算法确定他们被淘汰出局。

棒球淘汰问题似乎与这个问题最相似，但并非完全如此。

我应该如何建立最大流量问题的减少来适应这个问题？

谢谢你。

假设给定一个流网络 G=(V, E)，其中每条边的容量为 1。我想设计一个有效的算法来找到边 e，这样从 G 中删除它会导致 G' 的最大值较小（ s, t)-流量大于 G。

我想到了 G 的几个属性：

• 任何边的流都是二进制的；要么有流量，要么没有流量
• 增加一条边的流相当于在残差图上反转它
• 非零入边数 = 所有中间节点的非零出边数
• 改变 (s, t) 路径上的任何边会移除该路径中的所有流

除了运行 Ford-Fulkerson 并选择属于 min (s, t)-cut 的任何边之外，我想不出其他任何东西。

使用 G 仅包含容量为 1 的边这一事实，是否有更有效的算法？谢谢。

我有一个可以用图建模的问题，需要用 opl 实现它并用 Ford Fulkerson 算法应用最大化。我没有找到任何用opl制作的东西...

我们有一个流网络和两个节点u和v。我们想创建一个算法，告诉我们是否存在最小 st 割，使得它与u源节点属于割的同一侧，与汇节点属于割的同一侧。svt

我知道在运行 Ford-Fulkerson 后如何找到最小切割，但由于最小切割不一定是唯一的，我不确定如何测试在一侧和另一侧是否存在最小u切割。stv

我现在正在处理一项任务，因为我们正在进入我们的图论单元，它是福特 Fulkerson 算法的实现。这个想法是我们有一个带有一定数量节点的加权有向图。我们还提供了图本身，它是有向边和节点的集合，但是，鉴于节点和边的构造，我们必须使用边作为我们的遍历方法（它们是由起始节点、权重组成的对象，和结束节点）。

我已经降低了 DFS，但在实际生成最终加权图时遇到了困难。就目前而言，我能够获得正确的最大流量，但是我的边缘附加了错误的权重，目前甚至没有加起来到最大流量。我怀疑错误来自我如何计算残差图边缘的流量，因为它目前只是从当前权重值中减去流量。我知道在普通的福特 Fulkerson 中，每条边的残差都有两个方向，但在我实现它的方式中，我只有一个，因为 Graphs 的构造函数没有这样做。我还需要在最后返回我的残差以查看所有顶点的值及其权重，

福特富尔克森级

图形和边缘类

作为参考，我有输入

它定义了一个具有 5 个节点和 9 个边的起始​​图，它们的权重偏向一边。正确的输出是：

但是，在运行我的 Ford Fulkerson 时，我得到以下输出：

我一直在看下面的GeeksforGeeks 文章，其中他们从有向图开始，但后来不知何故能够以相反的方向访问顶点：

关于从哪里开始寻找或我做错了什么的任何指示或提示都会很棒。