给定一个有向加权图，如何找到所有顶点对之间的最大流量(或最小边切割)。天真的方法是简单地调用像 Dinic 的 Max Flow 算法，其复杂度为 O((V^2)*E) ，对于每一对。
因此，对于所有对，它是 O((V^4)*E) .
是否可以将复杂性降低到 O((V^3)*E)或到 O(V^3)通过一些优化？
最佳答案
Gomory-胡树不适用于有向图 ，撇开这一点不说，Gomory-Hu Tree 将通过应用最小割来形成 Graph 最大流。
时间复杂度为:
O(|V|-1 * T(minimum-cut)) = O(|V|-1 * O(2|V|-2)) ~ O(|V|^2)
* 使用最优 minimum-cut算法 ( Max-Flow Min-Cut Reduction )
此 example说明如何从给定的图构建 Gomory-Hu 树
关于graph - 所有对最大流量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13990689/