在广义网络中计算最大流量

Question

我正在寻找一个高效的、公开可用的算法，最好有实现，用于解决带有增益的广义（非纯）网络中的最大流问题。所有乘数、容量和流值都是非零整数。

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

- Wander Nauta

---

你所说的“非纯”的意思是什么？缺乏正常算法是指什么？ - Saeed Amiri

弧可以有增益，即进入弧的流量可以小于从中流出的流量。纯网络只会有乘数为1的弧。 - Wander Nauta

每个弧线都可以有不同的乘数吗？还是它们都将有相同的乘数？ - Saeed Amiri

每个弧可以有不同的乘数。 - Wander Nauta

我认为使用普通流算法没有问题，只需要在计算增广路径时选择一条使路径上的最小乘数在所有可能路径中被最大化的路径，并将流量增加为c*m（不仅仅是c），我认为这个正确性的证明并不难，稍后我会考虑。 - Saeed Amiri

嗨@WanderNauta，你有找到这个算法或实现吗？ - Cole Gleason

Answer 1

这里有一些算法和解释的链接：

1. http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm
2. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow
3. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2

这是我对最大流问题的解决方案：抱歉变量名称有些年轻气盛 :) http://infoarena.ro/job_detail/431616?action=view-source
希望它能帮到您。

- Mark

---

看起来这些都是针对非广义网络（即“正常”的网络，其中每个乘数都为1）的。 - Wander Nauta

Answer 2

第一个（强）多项式时间算法是由Végh在2013年发表的，此后已被Olver和Végh改进为最坏情况下运行时间为O((m+nlogn)mnlog(n^2/m))。 但我不知道这个算法是否有公共实现。

链接的论文还包含对早期（弱）多项式时间算法以及近似算法的引用，其中一些可能具有公共实现。 （Tardos和Wayne的这篇旧论文提到了一个C ++实现。）

- user4235730