algorithm - 具有增量更新的福特富尔克森算法的实现

Question

我已经实现了 Ford Fulkerson 算法，现在正在尝试研究它的变体。

假设给定的图及其解决方案是

假设在导出解之后，其中一条边的容量增加或减少。我们需要找到一种算法来使用当前解决方案而不是从一开始就获得新的最大流量。

我的建议是，对于这个例子，如果我们假设 1-3 边的容量从 12 减少到 8，那么我们需要从 1 到开始节点进行 BFS，并将每个边上的流量减少 4 并且做一个 BFS 从 3 到 5 并减少那里的流量。但我不确定这是否正确。即使它是正确的，我也不知道如何实现它？

谁可以帮我这个事？

Answer 1

是的，你的方法是正确的。

使用与查找最大流量相同的 BFS。

请记住：

• 你不能使用你正在调整的边缘。
• 边缘可能没有被充分利用，因此您可能只需要推回少量的流量。