algorithm - 在 Ford Fulkerson 算法中添加新边后有效计算最大流量？

Question

假设已使用 Ford-Fulkerson 计算出 G 的最大流量，并将具有单位容量的新边添加到 E。如何有效更新最大流量。 (t 不是必须更新的流的值，而是流本身。

Answer 1

设 G' 是新边 e 添加到 G 的图。请注意，我们保留了剩余边缘的容量和流量。

现在在 G' 中找到增广路径 p。

如果 p 存在，则将 G' 中沿该路径的流更新为 1。否则，流保持不变。

这给出了最终的流量值。这是正确的，因为如果 p 存在，那么它会通过 e。因此，沿 p 的流量更新恰好为 1。由于 Folk-Fulkerson 算法以积分步骤增加流量，因此在此次更新后 G' 中没有增广路径。

如果 p 不存在，则根据 mincut-maxflow 参数，这是最大流，因为 mincut 为 0。