algorithm - 添加边后更新最大流量

Question

考虑我们有一个网络流量，并且使用 Edmond-Karp 算法，我们已经有了网络上的最大流量。现在，如果我们向网络添加任意边（具有一定容量），那么更新最大流量的最佳方法是什么？我正在考虑更新关于新边缘的残差网络并再次寻找增强路径，直到我们找到新的最大流量，但我不确定它是否有效或者它是否是最好的方法！

Answer 1

After doing maxflow you know the amount of content each edge flowed.

So, when the cost of an edge changed you can do the following things :

1. Suppose, the content flowed by that edge is w.
2. Now do a forward dfs and a backward dfs from that edge and undone total w content from the edge it linked.

Here each edge is represented by x/y, where y means the edge capacity and x means the content it flowed.

Now you want to change the cost of edge 4->3 from 2 to 3.

您所要做的就是从边缘做一个forward and backward dfs从这些边缘4->3撤消的2权重作为4->3流动的w=2内容。

这是该过程将如下所示：

现在你几乎完成了:)

3. 改变边缘的成本，4->3一次2又一次3地尝试找到一条增广路径:)

如果您觉得难以理解或者我错了，请告诉我:)

编辑 ：

1. 如果新边缘成本大于当前成本，则您不必取消权重。您可以尝试找到一条改变边缘容量的增广路径。

2. 但是如果容量减少了，你就必须减轻重量并尝试找到增加的路径。

3. 如果添加了新边，您可以只添加边并尝试找到可用的增广路径。就是这样。

Answer 2

实际上添加一条新边并不是很困难——在添加边之前你有边的流量/容量，然后添加边及其逆。然后运行用于查找增广路径的算法，直到找到非零流，仅此而已。已经找到了大部分最大流量，因此（理论上）应该不会太慢。我不知道您使用的是哪种最大流量算法，所以我不能更具体，但是在添加新边之后，您可能会违反算法的属性，因此您会以次优方式找到最大流量。您仍然已经处理了大部分图表，所以这应该不是一个太大的问题。

I would recommend you to use Ford-Fulkerson algorithm to finish of the task no matter what the original algorithm you used for the max flow is. I think it will perform well in cases that most of the max flow is already discovered.