所有节点对最大流量

Question

给定一个有向带权图，如何找到所有顶点对之间的最大流量（或最小边割）。 朴素的方法是为每一对顶点调用一个最大流算法，如Dinic，其时间复杂度为O((V^2)*E)。因此，对于所有顶点对，时间复杂度为O((V^4)*E)。 是否可以通过优化将复杂度降低到O((V^3)*E)或O(V^3)呢？

- sabari

---

PS: This is not home work. - sabari

你有研究过Gomory-Hu树吗？ - mmgp

@mmgp：这正是我想要的。谢谢！你能发一个链接，介绍Gusfield算法并附带示例和伪代码吗？ - sabari

您可以通过访问实验链接找到代码：http://www.cs.princeton.edu/~kt/cut-tree/。 - mmgp

@mmgp，您能否把评论转换成答案呢？ - Pål GD

Answer 1

Gomory-Hu树不能处理有向图，但是它可以通过最小割形成图的最大流量。

时间复杂度为：

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

* 使用最优的最小割算法 (最大流最小割规约)

这个示例说明了如何从给定的图中构建 Gomory-Hu 树

- Khaled.K

---

Gomory-Hu树不适用于有向图（除非所有弧的容量（u，v）=（v，u））。割并不是对称次模函数，这是Gomory-Hu树工作所必需的。 - Chao Xu

@ChaoXu 谢谢您的评论，我会在我的答案中做出记录。 - Khaled.K

你的文本中提到T（最小割）的时间复杂度为O（2 |V| - 2）。这是什么算法？E-K算法的时间复杂度为O（|V| * |E|^2）~ O（|V|^5），Dinic算法的时间复杂度为O（|V|^2 * |E|）~ O（|V|^4），而Gomory-Hu算法的时间复杂度为O（|V|^5），而不是O（|V|^2）。 - Boyd Stephen Smith Jr.

Answer 2

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

目前尚未解决的问题是是否存在一种算法，可以更快地在有向图上解决所有对最大流的求解而不是运行n^2次最大流。

- Chao Xu