algorithm - 在福特富尔克森算法中添加新边后有效计算最大流量？

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。