考虑我们有一个网络流量，并使用 Edmond-Karp 算法，我们已经拥有网络上的最大流量。现在，如果我们向网络添加任意边（具有一定容量），更新最大流量的最佳方法是什么？我正在考虑更新关于新边缘的残差网络，并再次寻找增强路径，直到找到新的最大流量，但我不确定它是否有效或者是否是最好的方法！
执行 maxflow 后，您就知道每个边缘流动的内容量。
因此，当边的成本发生变化时，您可以执行以下操作：
- 假设该边流过的内容是
w.
- 现在做一个
forward dfs and a backward dfs从该边缘开始和未完成的总数w来自它链接的边缘的内容。
这里每条边都表示为x/y, where y意味着边缘容量和x指的是它流动的内容。
现在您想要更改边缘成本4->3 from 2 to 3.
你所要做的就是做一个forward and backward dfs from 4->3边缘和未完成2这些边缘的权重为4->3 flowed w=2内容。
该过程如下所示：
现在你快完成了:)
- 改变边的成本
4->3 from 2 to 3并再次尝试找到一条增广路径:)
如果您觉得很难理解或者我错了，请告诉我:)
Edit :
如果新边成本大于当前成本，则无需撤消权重。您可以尝试找到一条改变边缘容量的增强路径。
但如果容量减少了，你就必须减轻重量并尝试找到一条增强路径。
如果添加了新边，您只需添加该边并尝试查找增广路径（如果可用）。就是这样。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
