问题标签 [ford-fulkerson]

有人可以指导我到一个网站，该网站提供了有关如何在图表上应用福特-富尔克森方法以找到最大流量的分步说明。

非常感谢你。

我正在尝试使用 Ford-Fulkerson 算法解决图的最大流量问题。该算法仅用有向图描述。当图是无向的时怎么办？

我模仿无向图所做的是在一对顶点之间使用两条有向边。让我感到困惑的是：这些边缘中的每一个是否应该有一个残余边缘，或者“相反”的有向边缘是残余边缘？

我假设是最后一个，但我的算法似乎陷入了无限循环。我希望你们中的任何人都可以给我一些帮助。下面是我自己的实现。我在查找中使用 DFS。

我正在研究 Cormen 的“算法简介第 2 版”中的 Ford-Fulkerson 算法。有向图 G=(V, E) 的伪代码描述如下，其中 f 是在 VxV 上定义的流

残差图 Gf 具有与 G 相同的顶点，并且将 c(u, v) - f(u, v) > 0 的有序顶点对 (u, v) 作为边。（编辑：c 是容量函数在不属于图形的边上开始并扩展为零时给出）

我不确定在“双向”存在边的情况下该怎么做，例如当边及其反向在图中时算法中会发生什么。我假设最小值中的 c(u, v) 用于图中的原始容量。当 (a, b) 和 (b, a) 都是边时，我是否需要以某种方式处理残差图中的四个边？目前在我的设置中，我无法直接处理平行边缘。

我在 SO 上发现了以下问题： Maximum flow - Ford-Fulkerson: Undirected graph 但我不清楚结果是什么。

我正在尝试用 C++ 实现福特富尔克森算法。

但是，我的find_edge功能有问题。当我在 中调用此函数时my_alg，它会选择正确的边缘，然后在 中增加流量my_alg。它选择右边缘并增加其流量（flow），但是当我再次调用该find_edge函数时，流量并没有按应有的方式增加。

这导致我的算法无限循环。可能我对指针做错了什么。你可以在下面看到我的代码。

It is not even printing the "abc" in the cout statement. I am trying to implement the Ford-Fulkerson algorithm. Here I am reading from a file and initializing capacity flow matrices. After that I am calling maxflow function, which I have omitted here.

我正在使用 bfs 来查找增广路径。但它每次都产生相同的路径。但是福特富尔克森算法要求，我们每次从源到接收器都选择不同的路径，所以有人可以建议我如何修改 bfs 以使其产生不同的路径source 和 sink.graph 之间的每次路径都是有向和加权的

假设我们重新定义残差网络以禁止边缘进入s。认为程序 FORD-FULKESON 仍然正确地计算了最大流量。

我在想，当我们增加一条路径时，反向边缘的剩余容量会增加，如果需要，可以用来减少该边缘的流量（但总体上会增加网络流量）。因此，如果我们不允许边缘进入s，则意味着我们不允许边缘中的流量减少s- x（x与 相邻的节点s）。所以在我们允许边缘进入的情况下，s我们可以有一个循环

s to x_1 leadsto y leadsto x_2 to s to x_3 leadsto t

但是如果我们再次禁止边缘进入s，我们可以找到没有循环的相同路径。以上都是直观的想法，但我想要一个正式的证明。

问题来自Cormen 等人的《算法导论》。

到目前为止，我一直在处理顶点之间只有一条有向边的图。对于我用来测试我的实现的所有示例，已经产生了正确的答案。但是，当我使用包含具有两个方向的边的顶点的图时，我没有得出正确的答案。我一直将这种向后运行的边缘视为这两个顶点之间的回流，因为看起来回流和向后运行的不同“管道”最终将是等效的。我的假设是错误的吗？

我正在尝试用 Java 实现 Ford Fulkerson 算法。到目前为止，我有一个带有节点和边的图表。节点包含一个 ID 字符串和一个边的 adjacencyList。边包含容量和它通向的节点。

我正在尝试了解维基百科页面上的伪代码以及如何实现它（我正在使用 Java）。这是我目前所理解的：

1. 首先，我将图中所有边的流设置为零。（表示流的好方法是什么？直接在我的图的边中作为变量？）

2. 第二步是创建残差图，这是一个边缘具有残差容量的网络：容量 - 流量（“正常图”中的相应边缘）。然后，您使用此残差图找到从源到汇的路径，并找到沿该路径的最小容量。（这是事情变得非常棘手的地方，我应该为残差图创建一个全新的图，还是应该在原始图中以某种方式表示它？最好的方法是什么？）

重复第 2 步，直到找不到路径，但每次找到路径时，您都执行第 3 步和第 4 步：

1. 对于沿路径的每条边，您添加在步骤 2 中找到的最小值。

2. 对于路径相反方向的每条边，减去步骤 2 中找到的最小值。

第 3 步和第 4 步让我感到困惑，因为我觉得在一个方向上添加和在相反方向减去是一回事。这些加减法是在图中做的吧，不是残差图吗？

真的很感激一些帮助，我已经尝试了几个小时来解决这个问题，但我似乎无法理解它。

我正在做实现 Ford-Fulkerson 算法的作业，他们说我们应该使用 DFS 进行路径查找，但我被困在某个地方。我没有发布代码，因为它的本地化太多了。实际上我的 DFS 算法运行良好，但死胡同会导致问题，例如，如果我运行我的代码，我会得到这样的 DFS 输出

0=>1 1=>2 1=>3 3=>5

它从 0 开始，以 5 结束，但 1=>2 部分对我的算法来说是不必要的，我也使用 [N][2] 矩阵存储我的路径。我的问题是如何消除结果矩阵中的死胡同（也许在 DFS 递归内部？）