小编Ric*_*sol的帖子

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

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

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