Ford-Fulkerson 最大流求解方法
一瓜算法小册
在上一节"初识最大流问题"中,已经讲到了网络流中的一个经典问题 - 最大流问题.同上一篇的方式一样,这篇文章你要带着以下两个问题来阅读:
怎样搜索到一条增广路?
如何利用搜索到的增广路求解最大流问题?
Ford-Fulkerson 算法求最大流的原理是什么?
如何求得最大流
我们继续引用上文的例子:
假设有这么一个例子,这次 2019-nCoV 疫情让口罩变成了稀缺资源.所以,全国各地都在为武汉捐献物资.假设现在因为种种原因,我们只能通过地面线路来运输口罩物资,并且每一条线路是有流量限制的.假设不考虑运输速度,并且源点 S (杭州)的口罩物资产量是足够多的,