13-2: Ford-Fulkerson Algorithm 寻找网络最大流

讲解FF算法

感谢王老师！

Ford-Fulkerson算法

这个算法很慢，但是是可以得到正确的结果的。

下面我用实例来解释一下这个算法：

与之前的初始的可能有缺陷的找出最大流的算法相似，之前的三步都是先随便找出一条路径，然后计算出最小的路径的权值，更新闲置图。但是第四步是这个算法的突出：添加一个反向边。——也就是将第一步选中的路径中添加一系列绿色的反向边，各个反向绿色边的权值分别等于之前减去的边的权值。

在后续再找新的边的时候，也需要考虑相应的绿色边作为可以走过的路径片段，产生绿色边的过程中会有平行边，因此需要将平行边合并。这里要注意 的是绿色边和原先的边的性质是相同的，是可以当作一样的路径使用的。！

算法的时间复杂度是O(边数*最大流数量)

**************************************************

啊可以帮忙解释一下吗我还是没懂为什么不是所有443边都减？

绿色的边代表的是之前选中的路径的反悔的内容(举个例子 在第一次循环的时候要添加从v4到v1的绿色边，权值是3，也就是说 我在占用从v1到v4空闲值为3的水流之后，我并不能确认这3份的空闲值都需要用到从v1到v4的路径上，所以保险起见，我需要画出从v4到v1权值为3的绿色的边作为我反悔的内容)，

第三轮循环之前的图像

那么在第三轮循环，

只有s->v2->v4->v1->v3->t这一条路径可以选择，中间的v4->v1的绿色边的权值变为2 ，意思是说 “我认为原先从v1到v4流量为3的这种情况，流量设置的太多了，我返回一个单位的流量 ，将从v1到v4的权值为3的流量减少为2。至于减少的这一份流量放在了哪里？ 我根据后续添加的第三轮反向的绿线可以知道，这一份流量被安置在了从 v1到v3的路径上，” 那么为什么 从s到v1的4这个数值不用减一呢？ 是因为在第三次循环的路径上，根本就没有涉及到s->v1的这个路径。

其实我更想把第三次循环看成是将s->v1的四份水的流量，原先一开始是直接将其中的三份流量全部一股脑的送到v1到v4这个路径上去，后来发现其实将这三份的流量截出来一份的流量运到v1到v3的路径上更好，从这角度来说 s->v1的路径上的4份流量就不应该减一。