问题标签 [ford-fulkerson]

假设我在图 G = (V,E) 上运行了 Ford-Fulkerson 算法，结果是一个 max-flow f _max，它与一个 min-cut Xmin 相关联。我有兴趣通过增加图中任何一条边的容量来尽可能地增加流量。我怎样才能识别这个边缘？

一种策略可能是：给定初始顶点s和最终顶点t ，考虑从s到t的所有路径并验证容量较低的边。例如，如果我有一个 1/1 的边，这是我必须增加容量的顶点。

有解决这个问题的通用算法吗？

我正在自学最大流量，但出现了这个问题：

原来的问题是

• 假设我们有一个工作列表

  {J1，J1，...，Jm}

• 以及已申请的人员名单

  {P1, P2, P3,...,Pn}

• 每个人都有不同的兴趣，其中一些人申请了多个工作（每个人都有一份他们可以做的工作清单）

• 任何人不得从事超过 3 份工作。

所以，这个问题可以通过在下图中找到最大流量来解决

我理解这个解决方案，但是

问题的更难版本

如果加上这些条件呢？

• 简单版的前 3 个条件（工作和人员列表，每个人都有兴趣或能力列表）仍然相同

• 该公司仅雇用 Vi 人员担任 Ji

• 公司希望雇用尽可能多的人

• 一个人可以从事的工作数量没有限制。

我应该在图中做出什么改变，以便我的解决方案也能满足这些条件？或者如果我需要不同的方法，请告诉我。

在任何人说话之前，这不是功课。这只是自学，但我正在研究最大流量，问题出在那个区域，所以解决方案应该使用最大流量。

给定一个网络 G=(V,E) ，一个最大流 f 和一个 E 中的边 e，我需要找到一个 efficeint 算法来检测是否存在一些包含 e 的最小割。另一个问题是，如果我发现 e 包含在某个最小切割中，是否可以检测它是否是切割中最轻的边缘？

我考虑过运行 Ford-Fulkerson 算法，并增加/减少给定边缘的容量，看看会发生什么，但我还没有想出一些可以帮助我解决问题的方法。

如果有人能指出我的解决方案，我将不胜感激，在此先感谢。

Ford-Fulkerson 和 Edmonds-Karp 等。人。从零流量开始并增加它，直到它不能再增加。在正容量的情况下；但是，保证初始零流量既是合法流量，又是满足容量约束的流量。

对于负容量，全零的流量分配将无法满足容量约束，因此无法将其扩充为最大流量。

我在互联网上读到有人建议，负容量的最大流量可以作为两个最大流量问题来解决，但一直无法弄清楚如何去做......

所以让我解释一下这个问题：

给你一张图表。你找到最大流量。但事实证明，边 e_i 的容量错误。它少了一个。不幸的是，流量在旧容量下已达到极限。

一旦您被告知 e_i 容量错误，请在线性时间内计算新的最大流量（根据边和顶点的数量）。

这是我的计划：（1）你不能只在边上将边 e_i 处的流减少一个，因为你必须违反某些约束：就像流在边上是守恒的。修复流程，以便您可以获得有效的流程。但是怎么做？

（2）有人给我提示：显示有效流=先前流-1.mmm会有所帮助...

帮助。

为了在图中找到最大流量，为什么不考虑后边仅使该路径中具有最小边容量的所有增广路径饱和就不够了？我的意思是，如果我们假设从它流出，称它为后边缘有什么意义？

不知何故，我创建了这个图表，它似乎违反了流量值上限为最小切割容量的属性之一。
这是图表：

算法找到的最大流量为 7。（在 sact 上发送 3，在 sbt 上发送 3，在 sat 上发送 1）
而图中的最小切割是 {s,b} ，{a,c,t} 容量为 5。
我'我不确定我在哪里出错了。有人可以纠正这个吗？

我正在研究福特富尔克森，但对背景感到困惑。有人可以清除我直到什么时候或考虑图中背景的流量/容量条件应该是什么？因为我可以考虑任何边缘作为后端减去那么多流量并继续，这个过程可以继续下去。

请帮我。

谢谢

阿比纳夫

I'm trying to implement a Ford–Fulkerson algorithm in java and I've been having some problems where my code gets obnoxiously and unnecessarily complicated.

What I do want is to have:

Now I want to group nodes similarly how I would a (bidirectional) tree. Each node has a list of all nodes it's connected to.

My problem is this: How could I give this connection a value (maximum flow, current flow) ?

Should I make another class Connection that has Node A Node B and max flow / current flow. And if I do that, how should I connect the nodes ? (as in should every node have a Connection and wouldn't that be redundant ? I'm a bit stuck. edit Or should I just have Connections and implement some sort of search function to acomodate linking elements. It's all I can think of to be honest.

P.S.

This class is mostly just the math part, so I have never implemented a graph, nor does the course cover this, so thank you for helping a novice :) (that's if this doesn't get closed in like 5 minutes).

在我的分布式 Java 类中，我必须创建一个使用线程解决迷宫的算法。迷宫中的所有交叉点（多于一条剩余路径）将创建一个新线程，该线程将在旧线程中断的地方继续。最后我会查看所有路径，看看哪一个是有效的（从头开始，到最后）。

我想用Ford-Fulkerson 算法做同样的事情，但是这一次，我不必使用线程，我想避免这种情况，因为有一个线程会不断产生新线程，从而产生新线程（并且等等）似乎不必要的危险。

这是我的伪代码算法+一些信息：

该图是一个n矩阵n，其中int matrix [line][column]表示flow节点line index和节点之间column index（未连接的流为-1）

在主程序中我只是调用pathFinder(start,end)then PathFinder.getAllPaths()，并过滤无效路径（死胡同、循环）。好吧，实际上我计划在该run()部分中处理循环，但我还忘了这样做。这很容易。

最后，我有一个包含所有路径的静态变量（arrayList）。我验证哪些路径是“有效的”，就是这样。

我应该使这个递归而不是使用线程吗？还有其他解决方案吗？我应该发布实际代码（尽管它不完整）。