图论动画-Ford-Fulkerson最大流算法.ppt

《图论动画-Ford-Fulkerson最大流算法.ppt》由会员分享，可在线阅读，更多相关《图论动画-Ford-Fulkerson最大流算法.ppt（16页珍藏版）》请在三一办公上搜索。

1、15.082 和 6.855J,最大流问题的Ford-Fulkerson 增广路径算法,2,Ford-Fulkerson 最大流,4,1,1,2,2,1,2,3,3,1,s,2,4,5,3,t,这是初始网络，加上弧的反向.,3,Ford-Fulkerson 最大流,4,1,1,2,2,1,2,3,3,1,s,2,4,5,3,t,这是初始网络以及初始剩余网络.,4,4,1,1,2,2,1,2,3,3,1,Ford-Fulkerson 最大流,在G(x)中寻找任何s-t 路径.,s,2,4,5,3,t,5,4,1,1,2,1,3,Ford-Fulkerson 最大流,判定路径的容量 D.,在路径上

2、发送 D 单位的流.更新剩余容量.,1,1,1,2,1,2,3,2,1,s,2,4,5,3,t,6,4,1,1,2,1,3,Ford-Fulkerson最大流,寻找任何s-t 路径,1,1,1,2,1,2,3,2,1,s,2,4,5,3,t,7,4,2,1,1,1,1,2,2,1,1,1,1,3,Ford-Fulkerson 最大流,1,1,1,1,3,2,1,s,2,4,5,3,t,判定路径的容量 D,在路径中发送 D 单位的流.更新剩余网络,8,4,2,1,1,1,1,2,2,1,1,1,1,3,Ford-Fulkerson 最大流,1,1,1,1,3,2,1,s,2,4,5,3,t,寻找

3、任何 s-t 路径,9,1,1,1,1,1,4,1,2,1,1,2,1,1,3,Ford-Fulkerson 最大流,1,1,3,2,1,s,2,4,5,3,t,判定路径的容量 D,在路径中发送 D 单位的流.更新剩余网络,10,1,1,1,1,1,4,1,2,1,1,2,2,1,1,3,Ford-Fulkerson 最大流,1,1,3,2,1,s,2,4,5,3,t,寻找任何 s-t 路径,11,1,1,1,2,1,1,1,1,4,2,2,1,1,2,2,1,Ford-Fulkerson 最大流,1,1,3,1,1,s,2,4,5,3,t,2,判定路径的容量 D,在路径中发送 D 单位的流.

4、更新剩余网络,12,1,1,2,1,1,1,1,4,2,2,1,1,2,2,1,Ford-Fulkerson 最大流,1,1,3,1,1,s,2,4,5,3,t,寻找任何 s-t 路径,2,13,1,1,1,1,1,4,1,3,1,1,2,1,1,3,2,2,1,2,1,Ford-Fulkerson 最大流,2,1,s,2,4,5,3,t,2,判定路径的容量 D,在路径中发送 D 单位的流.更新剩余网络,14,1,1,1,1,1,4,1,3,1,1,2,1,1,3,2,2,1,2,1,Ford-Fulkerson 最大流,2,1,s,2,4,5,3,t,2,在剩余网络中没有 s-t 路径.此流是最优的.,15,1,1,1,1,1,4,1,3,1,1,2,1,1,3,2,2,1,2,1,Ford-Fulkerson 最大流,2,1,s,2,4,5,3,t,2,这些是从结点 s 可达的结点.,s,2,4,5,3,16,Ford-Fulkerson 最大流,这是最优流.,