graph - 所有对最大流量

Question

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

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

Answer 1

Gomory-Hu Tree不适用于有向图，除此之外，Gomory-Hu Tree 将通过应用最小割来形成 Graph 最大流。

时间复杂度为：

O(|V|-1 * T(minimum-cut)) = O(|V|-1 * O(2|V|-2)) ~ O(|V|^2)

* 使用最优最小切割算法（Max-Flow Min-Cut Reduction）

这个例子说明了如何从给定的图构造 Gomory-Hu 树

Answer 2

Gomory-Hu 树不适用于有向加权图。

是否存在比在有向图上运行 n^2 个最大流更快地解决所有对最大流的算法是一个悬而未决的问题。