问题标签 [max-flow]

是否有一个快速的 cython/python 库来进行最大流量/最小切割计算（最好使用 Boykov-Kolmogorov），它具有 BSD 许可证？

轻量级 C 库也很有用。

我正在以下链接阅读推流算法。

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxflowPushRelabel

提到了多余流量 - 我们将多余流量 e 定义为 e(u) = f(V,u)，即流入 u 的净流量。如果 e(u) > 0，则顶点 u ∊ V-{s,t} 溢出/激活。

我正在寻找简单流网络的示例，我们如何计算 e(u) ？

感谢您的时间和帮助。

V wrt 中顶点的有效标记。预流 x 是一个函数 d[.] : V -> Z 满足：

d[s] = n ^ d[t] = 0

对于所有 (v,w) 属于 E ： d[v] <= d[w] + 1

假设我们有 4 个顶点，包括 (s 和 t)

那么我们有 d[s] = 4

根据有效标签，我们应该有 d[v] <= d[w]+1，但是对于来自 's' 的边，它是无效的，因为 4 <= 1 是假的。难道这个逻辑不仅是来源吗？

我理解正确吗？请纠正我。

感谢您的时间和帮助

我正在阅读 Cormen 等人的算法简介中的推流算法。

我很难理解引理 26.20，如下所述：

令 G = (V, E) 为源 s 和汇 t 的流网络，设 f 为 G 中的预流。那么，对于任何溢出的顶点 u，在残差网络 Gf 中存在从 u 到 s 的简单路径.

要查看此 leema 的上下文，可以在以下链接中找到。

http://integrator-crimea.com/ddu0164.html

请求您的帮助以了解这一点。

感谢您的时间和帮助。

给定一个无向图 G = (V, E)，G 中的边具有非负权重。

[1] 如何找到两个节点 s 和 t 之间的所有边不相交和等成本路径？

[2] 如何找到两个节点 s 和 t 之间的所有边不相交路径？

[3] 如何找到两个节点 s 和 t 之间的所有顶点不相交和等成本路径？

[4] 如何找到两个节点 s 和 t 之间的所有顶点不相交路径？

任何近似算法代替？

我在课堂测试中遇到了一个问题。在图书馆里，每个成员要四本书，而每本书只有两个成员要。此信息以二分图 G = ( X + Y , E ) 的形式给出

X：所有成员的集合 Y：所有书籍的集合 Edge E = 边的集合 (x,y)，其中 x 是为书籍 y 请求的成员。我们必须找到图书馆员最多可以给每个成员两本书的方式，以使最多的成员满意。

我提出了两种方法：

1. 引入两个新顶点 s(source) 和 t(destination)。将边从 s 引入 X 中容量为 2 的所有成员。所有边 E 的容量为 1，新边 Y 到 t 的容量为 1。现在应用 Max flow 算法找到最大匹配。最大匹配是所需的解决方案。
2. 另一种方法是通过引入相同的边来遵循与上述相同的算法，但每条边的容量为1。现在找到最大匹配。此匹配将为最多成员提供一本书。删除匹配的书籍并再次应用上述算法。再次删除匹配的书籍和拥有两本书的成员，并再次应用算法，直到 X 和 Y 之间没有边缘。获得的解决方案是所需的解决方案。

虽然我得到了上面的算法，但我不确定哪个是正确的，或者没有一个是正确的。如果还有其他算法，请在此处提出建议。

我想很快解决很多小型 DAGS（8-12 个节点，20-60 个边）上的最小切割问题。看起来最好的解决方案是解决最大流量并从中推断出一个削减。有相当多的最大流算法可以进行理论和经验时序比较，但是这些都假设有趣的是随着图表越来越大的性能。人们还经常提到，使用的复杂数据结构的设置时间可能非常长。那么给定一个仔细、优化的实现（可能在 C++ 中），哪种算法在小图上初始化和运行速度最快？（我天真的假设是 Edmonds-Karp 在数据结构方面可能很简单，因此会击败更复杂的算法，但这只是一个猜测。）

在我深入探讨这个问题之前，这里有一些我已经拥有的背景信息：

-我首先创建了一个基于美国城市的无向邻接矩阵图，边权重是计算距离（通过距离公式实现）。

-我还使用 prim 算法实现了最小生成树。

现在我需要实现我拥有的 Edmonds Karp 最大流量算法，但我对如何根据我拥有的数据创建容量图以实现以下代码中使用的算法感到困惑：

任何帮助将不胜感激，谢谢！

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

给定一个有向加权图，如何找到所有顶点对之间的最大流量（或最小边切）。
天真的方法是简单地调用像 Dinic 的Max FlowO((V^2)*E)算法，其复杂性是，对于每一对。
因此对于所有对它都是O((V^4)*E)。

是否有可能通过一些优化O((V^3)*E)来降低复杂性？O(V^3)