问题标签 [ford-fulkerson]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
1 回答
661 浏览

algorithm - 如何在具体问题中实现 Ford-Fulkerson?

我正在做一个特定的练习,我被卡住了。

要解决:

解决流通需求问题。有些工厂生产货物,有些村庄必须交付货物。它们由道路网络连接,每条道路都可以容纳最大数量的货物通过它。问题是找出是否有满足需求的流通量。这个问题可以转化为最大流量问题。假设每个工厂节点 fi 都有一个生产率 pi。另外,那个di 是vi 村的需求率。您的输入将是使用其每个节点的邻接列表给出的图形。最初给出一个描述图节点数量的数字,然后是每个节点的邻接列表的一行(连同容量),例如“da 10 c 5”表示节点 d 连接到 a(容量为 10)和到 c(容量为 5)。

据我了解,我需要这样的输入文件:

我已经得出结论,我应该使用 Ford-Fulkerson 算法来找到最大流量(因为这是要求的输出)

环顾算法的不同实现(我正在考虑使用 C 或 Java 对其进行编码),我偶然发现了以下问题:

Ford-Fulkerson 仅适用于 1 个源和 1 个接收器。在这个问题中,我们有测试用例,例如有 3 个工厂和 2 个村庄。有人可以启发我,因为我真的被卡住了。

0 投票
0 回答
72 浏览

algorithm - 有向平面图中最大 st 流的 O(n * log(n)) 算法(Borradaile,Klein)

有人可以用一个例子向我解释 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 算法的示例。

谢谢你。

0 投票
1 回答
200 浏览

algorithm - Ford Fulkerson 算法增加流量

关于带有路径的Ford Fulkerson算法,s-x-y-z-t我们必须找出如何增加沿该路径的流量。

我遇到的问题是,我不知道如何获得解决方案中的值。
有人可以解释吗?

在此处输入图像描述

0 投票
1 回答
171 浏览

r - 从 R 中的 maxFlowFordFulkerson 恢复最大二分匹配

我想找到最大的二分匹配,所以我将使用 Flow Ford Fulkerson 算法,如此处所述

但是当我实现这个函数时,我只得到了最大流量的值,但我感兴趣的是流量本身,这样我才能找到匹配的。

有谁能够帮我?

maxFlowFordFulkerson在R中使用了这个函数。

0 投票
1 回答
837 浏览

java - 修改 Java Ford Fulkerson 实现以打印最大流量解决方案中每个边缘使用的最大流量?

我想修改Ford-Fulkerson 算法的这个实现(也在下面发布),以便我可以绘制节点并分析数据。我不仅想输出最大流量,还想输出每个边缘的最大流量,例如,如果最大流量为 50,并且它使用从节点 1 到 3 的流量,值为 10 我想打印它1 - 3 - 10 或类似的格式。我试过打印 u 和 v,然后是残差 [u][v],但它看起来不正确。有任何想法吗?

0 投票
1 回答
219 浏览

algorithm - 关于增广路径的问题(Ford-Fulkerson 方法)

我现在正在学习 Ford-Fulkerson 方法。

有些文章说如果 f 是最大流,那么就没有增广路径! 但是如果没有增广路径,你怎么知道 f 是最大流量?

  • 你怎么知道寻找增广路径的方法是正确的?
  • 在残差网络中,为什么如果我们不能从 s 到达 t 就没有办法增加流量?你怎么知道?
0 投票
0 回答
85 浏览

algorithm - 最短路径长度与最小切割能力的关系

在每个弧容量为 1 且从 s 到 t 的最短长度为 k 的图 G 中,最小容量 st 切割为 O(n^2/k^2),其中 n 是顶点数。n 选择 2 给出 O(n^2) 弧数,我不确定如何进一步推理以证明该陈述的合理性。如果我认为每条 st 路径都是 k 长,那给了我 O(n^2/k) 可能的交叉点。也许我的想法不太对。任何类型的输入将不胜感激

0 投票
0 回答
145 浏览

java - 如何修改 Ford-Fulkerson 最大流算法来打印访问过的节点?

我需要修改最大流量算法,以便我可以查看与最大流量相关的路径。无需打印与图相关的所有节点我想打印具有相应容量的图的最大流量的路径。

例如:- 它应该看起来像这样,

**

** 因此,通过添加容量可以验证最大流量,因为两个值相同。

请帮我解决这个问题,在此先感谢。

公共类 MaxFlow_Ford_Fulkerson {

** *

* **

0 投票
1 回答
32 浏览

flow - 基于福特富尔克森的算法会有死胡同吗?

我们能否像我们在 dinics 算法中所做的那样,在ford fulkerson merhod 中移除那些在 DFS 期间不会导致下沉 t 的边?如果没有,请您举个例子。

0 投票
1 回答
1171 浏览

r - R:Ford-Fulkerson 最大流量分步计算?

我目前正在研究基于 R 文档中的以下代码的 Ford-Fulkerson 算法:

& 得到以下结果:

结果表明该网络的最大流量为6。

但是,我一直在尝试手动计算最大流量,无论我做什么,我得到的最大流量都只有 5。

这是我能够根据代码示例映射的可能图表: 最大流量图

&我能够得到的一些可能的流程:

2 --> 4 --> 5 --> 6.......[容量:1]

2 --> 5 --> 4 --> 6(回流)...[容量:1]

2 --> 5 --> 6..........................[容量:1]

2 --> 4 --> 6..........................[容量:2]

[总容量:5]

或者

2 --> 3 --> 5 --> 6.......[容量:1]

2 --> 4 --> 5 --> 6.......[容量:1]

2 --> 5 --> 4 --> 6(回流)...[容量:1]

2 --> 4 --> 6.................................[容量:2]

[总容量:5]

我误解了这个过程吗?任何人都可以写下逐步获得最大流量 6 的路径吗?