仅通过更改一个边来增加Ford-Fulkerson算法的流量

Question

假设我在图G =（V，E）上运行了Ford-Fulkerson算法，并且结果是最大流f_max，它关联到最小割Xmin。 我希望通过增加图中任意一条边的容量来尽可能地增加流量。 我如何识别这条边？

一种策略可能是：给定初始顶点s和终点顶点t，考虑从s到t的所有路径并验证具有较低容量的边。例如，如果我有一条1/1的边，那么这就是我必须增加容量的边。

是否有解决此问题的通用算法？

- Richard Gasol

Answer 1

一旦您在图中找到了最大流，增加边（u，v）的容量只有在剩余图中存在从s到u和从v到t的正容量路径时才会增加最大流。如果不是这种情况，则在进行增加后，剩余图中将没有增广路径，因此最大流将保持不变。

具有此属性的边（u，v）中，您可以从s推送到t的额外流的最大量将受到限制。如果您可以通过该边推动任何流量，则必须通过找到从s到u的路径和从v到t的路径来实现。在这样做时，每个路径中都将有一个瓶颈边，并且流量不能增加超过这个值。因此，解决问题的一种选择是执行以下操作：

1. 在剩余图中查找从s到可达于s的每个其他节点的最大瓶颈路径。 2. 在剩余图中查找每个可以到达t的节点到t的最大瓶颈路径。 3. 对于跨越路径的每条边（u，v），可以通过的额外流的最大量由从s到u的max-bottleneck路径和从v到t的max-bottleneck路径的最小值给出。

换句话说，如果您可以计算图中的最大瓶颈路径，则可以在时间O（B（m，n）+ m）内找到应增加容量的边，其中B（m，n）是计算图中最大瓶颈路径的成本。

幸运的是，这是一个经过深入研究的问题，并且可以使用Dijkstra算法的变体来解决，其中存储到每个节点的最小成本路径被替换为存储到每个节点的最大瓶颈路径。通过快速搜索，您可以找到有关此问题的其他信息。使用斐波那契堆，您可以在时间O（m + n log n）内实现此搜索，因此确定应增加容量的边的总运行时间也应为O（m + n log n）。

希望这能帮助您！

- templatetypedef

---

好的解释，但有一个问题。使用增广算法，是否可以在时间O(k*|E|)内计算相对于新容量的最大流量，其中k是我们增加边缘容量的数量？我不太清楚，您能否告诉我我是正确还是错误的？还有一件事，最大流量的最大增加量将是多少？ - user1261015