在Ford-Fulkerson之后只改变一条优势,增加流量

Question

假设我在图G =(V,E)上运行Ford-Fulkerson算法,结果是最大流量f _max,它与最小切割Xmin相关联.我有兴趣通过增加图中任何一个边的容量来尽可能地增加流量.我如何识别这个边缘？

一种策略可能是:给定初始顶点s和最终顶点t,考虑从s到t的所有路径并验证具有较低容量的边缘.例如,如果我有1/1的边,这是我必须增加容量的顶点.

是否有解决此问题的通用算法？

Answer 1

一旦找到了图中的最大流量,如果从s到u以及从残差图中的v到t存在正容量路径,则增加边沿(u,v)的容量将仅增加最大流量.如果不是这种情况,那么在增加之后残差图中将不存在增强路径,因此最大流量将保持最大.

在具有此属性的边(u,v)中,在增加(u,v)的容量之后,可以从s推到t的最大额外流量将是有界的.如果你可以推动任何流过这条边,你必须通过找到从s到u的路径和从v到t的路径来实现.这样做时,两条路径中的每条路径都会出现瓶颈边缘,并且流量不会增加超过此值.因此,解决问题的一个选择是执行以下操作:

• 找到从s到残差图中s可到达的每个其他节点的最大瓶颈路径.
• 找到每个节点中可以在残差图中达到t到t的最大瓶颈路径.
• 对于穿过路径的每条边(u,v),可以通过边缘推动的最大额外流量由s到u的最大瓶颈路径的最小值和从v到t的最大瓶颈路径给出.

换句话说,如果你可以计算图中的最大瓶颈路径,你可以找到应该在时间上增加的边O(B(m,n)+ m),其中B(m,n)是成本计算图中的最大瓶颈路径.

幸运的是,这是一个经过充分研究的问题,可以使用Dijkstra算法的变体来解决,而不是将最小成本路径存储到每个节点,而是存储每个节点的最大瓶颈路径.快速谷歌搜索应该提供一些额外的信息.使用Fibonacci堆,您可以在时间O(m + n log n)中实现此搜索,因此用于识别容量应该增加的边的总运行时间也应该是O(m + n log n).

希望这可以帮助!