添加边缘后更新最大流量

Question

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

Answer 1

做maxflow后，你知道每个边缘流动的内容的数量。

所以，当边的成本变化，你可以做以下的事情：

1. 假设，内容流由边缘w。
2. 现在做一个forward dfs和一个backward dfs从边缘和撤消总共w内容从它连接的边缘。

在此，每个边缘由x/y，其中y意味着边缘容量和x表示意味着它流动的内容。

现在您想将边缘4->3的成本从2更改为3。

所有你需要做的就是做从4->3边缘forward and backward dfs和撤消2重量从这些边缘为4->3流入w=2内容。

下面是该过程将是这样的：

现在你几乎完成:)

更改边缘4->3从2成本到3并再次尝试找到扩充路径:)

让我知道如果你发现它是二fficult理解或者如果我错了不知何故:)

编辑：

1. 如果新的边缘成本大于目前的成本比你将不必撤销的重量。你可以尝试找到一个改变边缘容量的增强路径。

2. 但如果容量减少，你要撤消的重量，并设法找到可增广路。

3. 如果一个新的边缘添加，你可以添加边缘，并尝试如有发现可增广路。而已。

Answer 2

实际上添加一个新的边并不是很困难 - 在添加边之前您已经有了边的流量/容量，然后添加了边和它的倒数。然后运行你用来寻找扩充路径的算法，直到找到非零流量，就是这样。大部分最大流量已经被发现，所以这应该（理论上）不会太慢。我不知道你正在使用哪种最大流量算法，所以我不能更具体，但可能在添加新边缘后违反了算法的属性，从而以最优方式找到最大流量。你仍然已经处理了大部分图表，所以这不应该是一个太大的问题。

无论您用于最大流量的原始算法是什么，我都会建议您使用Ford-Fulkerson算法来完成任务。我认为在大多数最大流量已经被发现的情况下，它会表现良好。