添加一条边后更新最大流量

Question

添加一条边后更新最大流量

algorithmgraphmax-flowford-fulkersonedmonds-karp

4

考虑我们有一个网络流，并使用Edmond-Karp算法，我们已经在网络上获得了最大流量。现在，如果我们向网络中添加一条任意边（具有一定的容量），那么更新最大流量的最佳方法是什么？我考虑更新新边缘相关的剩余网络，然后再寻找增广路径，直到找到新的最大流，但我不确定它是否有效或者是否是最佳方法！

- Nima

2个回答

0

实际上，添加一条新的边并不难 - 在添加边之前，您已经有了边的流量/容量，然后您添加边及其逆变。然后运行用于查找增广路径的算法，直到找到非零流为止，就完成了。大多数最大流已经被找到，因此这应该不会（理论上）太慢。我不知道您使用的最大流算法是哪个，因此无法更具体地说明，但是在添加新的边之后，可能会违反算法的属性，因此您以次优的方式找到最大流。但仍然可以处理大部分图形，因此这不应该是一个太大的问题。

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

- Ivaylo Strandjev

实际上，我正在使用Edmond-Karp算法，它是Ford-Fulkerson的变体。唯一的区别是，在查找增广路径的每个步骤中，它使用BFS，因此它将具有最少的边数。这使得我们可以证明，在整数容量的情况下，我们可以在多项式时间内完成工作！ - Nima

好的。这样做甚至更好。 - Ivaylo Strandjev

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ali Akber · Accepted Answer

在执行最大流算法之后，您将知道每条边流动的内容量。

因此，当边的费用发生变化时，可以执行以下操作：

1. 假设该边流过的内容为w。 2. 现在从该边执行一个前向dfs和一个反向dfs，并从它连接的边中撤消总共w的内容。 3. 现在要将边4->3的成本从2更改为3。 4. 您需要做的全部是从4->3的边开始进行前向和后向dfs，并从这些边中撤消2的重量，因为4->3流了w=2的内容。 5. 然后你就完成了：） 6. 将边4->3的成本从2更改为3，然后再尝试找到增广路径:)

如果您发现难以理解或有错误，请告诉我：）

编辑：

1. 如果新的边缘成本高于当前成本，则无需撤消权重。您只需更改边缘容量并尝试查找增广路径即可。 2. 但是，如果容量减少，则必须撤消权重并尝试查找增广路径。 3. 如果添加了新边，则只需添加该边即可（如果可用），然后尝试查找增广路径。