网络流fordfulkerson算法.ppt

《网络流fordfulkerson算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、15.082和6.855J最大流问题的Ford-Fulkerson增广路径算法Ford-Fulkerson最大流4112212331s2453t这是初始网络，加上弧的反向.2Ford-Fulkerson最大流4112212331s2453t这是初始网络以及初始剩余网络.34112212331Ford-Fulkerson最大流在G(x)中寻找任何s-t路径.s2453t4411213Ford-Fulkerson最大流判定路径的容量D.在路径上发送D单位的流.更新剩余容量.111212321s2453t5411213

2、Ford-Fulkerson最大流寻找任何s-t路径111212321s2453t64211112211113Ford-Fulkerson最大流1111321s2453t判定路径的容量D在路径中发送D单位的流.更新剩余网络74211112211113Ford-Fulkerson最大流1111321s2453t寻找任何s-t路径811111412112113Ford-Fulkerson最大流11321s2453t判定路径的容量D在路径中发送D单位的流.更新剩余网络9111114121122113Ford-Fulke

3、rson最大流11321s2453t寻找任何s-t路径101112111142211221Ford-Fulkerson最大流11311s2453t2判定路径的容量D在路径中发送D单位的流.更新剩余网络11112111142211221Ford-Fulkerson最大流11311s2453t寻找任何s-t路径2121111141311211322121Ford-Fulkerson最大流21s2453t2判定路径的容量D在路径中发送D单位的流.更新剩余网络131111141311211322121Ford-Fulke

4、rson最大流21s2453t2在剩余网络中没有s-t路径.此流是最优的.141111141311211322121Ford-Fulkerson最大流21s2453t2这些是从结点s可达的结点.s245315Ford-Fulkerson最大流1122212s2453t这是最优流.16