最大流算法的运行时间

Question

我有以下两个问题。

1. 正误：我们总是能在Ford-Fulkerson算法中找到一系列的流增广s-t路径，这些路径能够让我们在多项式次迭代后达到最大流量。
2. 正误：我们总是能在Ford-Fulkerson算法中找到一系列的流增广s-t路径，但只有经过指数次迭代后才能达到最大流量。

- arkham knight

Answer 1

第一个答案肯定是false。因为Ford-Fulkerson算法的运行时间不是多项式，而是指数级别。

因此，为了找到所有的s-t路径以达到最大流量，需要指数级别的时间。

Ford-Fulkerson算法的运行时间为O(nV)，更精确地说是O((n+m)V)，其中n是节点数，m是图中边的数量，V是图的最大容量。

因此，它看起来像是一个多项式时间算法。然而，如果V很大，假设这个大数字可以表示为2^k，那么运行时间变成了O(n. 2^k) - 这是指数级别的。

第二个答案在某些情况下也不完全正确，但大多数情况下是正确的，如果您考虑图中容量值为整数/有理数。我们知道该算法需要指数时间-这没有问题。然而，如果图的容量值是无理数，那么Ford-Fulkerson算法不能保证终止。因此，第二个陈述也有一定的错误。然而，对于大多数情况来说，它是正确的，因为在大多数情况下，容量都是整数或有理数值。

- Reaz Murshed

Answer 2

第一个说法是正确的。第二个说法是错误的。

G_f表示G剩余网络，c_f是G_f中的容量。 这是我所知道的Ford Fulkerson方法：

1) Define: f(u,v) = 0, for all (u,v) in E.

2) while there exits a path p from s to t, in G_f:

    3)     c_f(p) = min{c_f(e) : for all e in p}

    4)     for (u,v) in p:

        5)         if (u,v) in E:

            6)             f(u,v) += c_f(p)

        7)         else:

            8)             f(u,v) -= c_f(p)

在过程结束时，f是最大流量。（你可以在CLRS的《算法导论》中阅读证明）

该算法的运行时间为O(X(V + E))，其中X是while循环迭代的次数。

现在，我们可以使用BFS搜索在第2行找到p。这种方法确保我们迭代while循环O(VE)次。此实现也称为Edmonds-Karp算法。因此，总运行时间为：O(VE*(E+V))。

这应该回答了您的第一个问题——我们始终可以通过在多项式时间内增广s-t路径来找到最大流量。

关于您的第二个问题： 考虑一个所有容量都为1的图G。显然，最大流量小于|E|。

由于while循环的每次迭代都将流f的当前值增加一个正整数（实际上是增加1。如果您需要证明，请参见CLRS），因此我们可以得出while循环最多迭代|E|次。 因此，无论我们如何选择增广路径，运行时间均为O（E *（E + V））。 这张图与第二个声明相矛盾。

- NG_