algorithm - 最大流算法运行时间

Question

我有以下两个问题。

1. 判断对错:我们总能在 Ford-Fulkerson 算法中找到一系列流量增加的 s-t 路径，以便我们在多项式迭代次数中达到最大流量。
2. 判断对错:我们总能在 Ford-Fulkerson 算法中找到一系列流量增加的 s-t 路径，这样我们仅在指数级迭代后才达到最大流量。

Answer 1

第一个答案肯定是错误的。因为 Ford-Fulkerson 算法的运行时间不是多项式的——它是指数的。

因此为了找到所有 s-t 路径以达到最大流量将花费指数时间。

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

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

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