问题标签 [max-flow]

是否有可靠且有据可查的 Python 库，该库可以快速实现算法，在有向图中找到最大流和最小割？

来自python-graph的pygraph.algorithms.minmax.maximum_flow解决了这个问题，但它非常缓慢：在具有 4000 个节点和 11000 个边的有向图中找到最大流和最小切割需要 > 1 分钟。我正在寻找至少快一个数量级的东西。

赏金：我在这个问题上提供赏金，看看自提出这个问题以来情况是否发生了变化。如果您对推荐的图书馆有个人经验，则可以加分！

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

非常感谢你。

我需要在图表上找到最小切割。我一直在阅读有关流网络的文章，但我能找到的只是最大流算法，例如 Ford-Fulkerson、push-relabel 等。鉴于最大流-最小切割定理，是否可以使用其中一种算法来找到使用最大流算法的图上的最小切割？如何？

到目前为止我发现的最好的信息是，如果我发现“饱和”边缘，即流量等于容量的边缘，这些边缘对应于最小切割。真的吗？这对我来说听起来不是 100% 正确的。确实，最小切割上的所有边缘都会饱和，但我相信也可能存在超出最小切割“路径”的饱和边缘。

我必须编写一个程序，该程序需要在有向流程图中维护一些数据。我需要在运行时计算最大流量。

我知道存在多个用于处理图的库，几乎实现了所有经典算法，但我的问题是我的图是动态的，这意味着它会在运行时演变。每次进化后，我都需要重新计算新的最大流量。

进化是：

• 添加边缘
• 增加边缘的容量

我需要重新计算的是从源 S 到在该步骤已修改的边缘的目标节点的最大流量。例如：

考虑到我的图表中进化的非常特殊的性质，哪个算法/库会更节省时间？我的意思是，考虑到每一步的图形几乎与上一步相同（除了一条边），是否有一种算法可以有效地重用其先前计算的中间结果？

我知道目的地每次都不同的事实使问题有点困难......关于我如何在每一步都比 O(VE^2) 更好的想法？

如果我也考虑这种可能的演变呢？

• 删除一个节点（以及该节点的所有传入/传出边）

我试图理解所有标准算法并思考如何修改它们，但由于图论不完全是我的领域，我惨遭失败......

任何帮助将不胜感激。谢谢。

我正在寻找快速算法来计算动态图中的最大流量（添加/删除具有相关边的节点到图）。即我们在 G 中有最大流量现在添加/删除了相关边的新节点，我不喜欢重新计算新图的最大流量，事实上，我想使用该图以前可用的结果。

任何不是很消耗时间/内存的预处理都会被占用。

最简单的想法是重新计算流量。

另一个简单的想法是这样，保存之前 maxflow 计算中使用的所有扩充路径，现在添加 vertex v，我们可以找到从源开始的简单路径（在上一步更新的容量图中），v然后到达目的地，但是问题是这条路径应该很简单，对于这种情况，我找不到比 O(n*E) 更好的方法。（如果只是一条路径或路径不相交，这可以在 O(n+E) 中完成，但事实并非如此）。

同样对于删除上述想法的节点也不起作用。

此外，我的问题与另一个关于动态边缘添加/删除的问题无关。

我很难理解来自 CLRS 的以下引理：

_{设 G 是一个流网络，s 和 t 是源和汇节点，f 是从 s 到 t 的预流，h 是 G 上的高度函数。那么在残差图 G f}中没有从 s 到 t 的增广路径.

为什么是这样？

我的算法的一部分需要计算具有整数容量的网络中的最大流量。我想使用 boost::edmonds_karp_max_flow 算法来找到最大流量。

我尝试阅读文档，但这对我来说非常困难，因为我以前从未使用过 BGL。我创建了如下图，其中Edge必须将权重属性用作图中边的容量。

我的目标是编写以下函数

有人可以用一个例子告诉我如何实现这个功能吗？

我会实现Edmond Karp 算法，但它似乎不正确而且我没有得到正确的流程，请考虑以下图表和从 4 到 8 的流程：

算法运行如下：

先找4→1→8，再找4→5→8，再找4→1→6→8

而且我认为第三条路径是错误的，因为使用这条路径我们不能使用 6→8 的流（因为它使用过），实际上我们不能使用 4→5→6→8 的流。

事实上，如果我们选择 4→5→6→8，然后是 4→1→3→7→8，然后是 4→1→3→7→8，我们可以获得更好的流量（40）。

我从 wiki 示例代码中实现了算法。我认为我们不能使用任何有效的路径，实际上这种贪婪的选择是错误的。

我错了吗？

代码如下（c#中阈值为0，不影响算法）：

我需要找到一个线性算法（O（|V| + |E|），它可以在原始最大流量已知但每条边的容量增加 1 的图上找到最大流量。

我正在尝试找到一种有效的、公开可用的算法，最好是通过实现来解决具有增益的广义（非纯）网络中的最大流量。所有乘数、容量和流量值都是非零整数。

是否存在这样的算法，或者这个问题不能在多项式时间内解决？