Ford-Fulkerson-最大流算法.ppt

Click to edit Master title style,Click to edit Master text styles,Second Level,Third Level,Fourth Level,Fifth Level,*,*,15.082,和,6.855J,最大流问题的,Ford-Fulkerson,增广路径算法,Ford-Fulkerson,最大流,4,1,1,2,2,1,2,3,3,1,s,2,4,5,3,t,这是初始网络，加上弧的反向,.,2,Ford-Fulkerson,最大流,4,1,1,2,2,1,2,3,3,1,s,2,4,5,3,t,这是初始网络以及初始剩余网络,.,3,4,1,1,2,2,1,2,3,3,1,Ford-Fulkerson,最大流,在,G(x,),中寻找任何,s-t,路径,.,s,2,4,5,3,t,4,4,1,1,2,1,3,Ford-Fulkerson,最大流,判定路径的容量,D.,在路径上发送,D,单位的流,.,更新剩余容量,.,1,1,1,2,1,2,3,2,1,s,2,4,5,3,t,5,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,6,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,单位的流,.,更新剩余网络,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,寻找任何,s-t,路径,8,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,单位的流,.,更新剩余网络,9,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,路径,10,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,单位的流,.,更新剩余网络,11,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,12,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,单位的流,.,更新剩余网络,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,在剩余网络中没有,s-t,路径,.,此流是最优的,.,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,可达的结点,.,s,2,4,5,3,15,Ford-Fulkerson,最大流,1,1,2,2,2,1,2,s,2,4,5,3,t,这是最优流,.,16,