《图论动画-Ford-Fulkerson最大流算法.ppt》由会员分享，可在线阅读，更多相关《图论动画-Ford-Fulkerson最大流算法.ppt（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、15.082 和和 6.855J 最大流问题的最大流问题的Ford-Fulkerson 增广路增广路径算法径算法Ford-Fulkerson 最大流最大流4112212331s2453t这是初始网络以及初始剩余网络这是初始网络以及初始剩余网络.34112212331Ford-Fulkerson 最大流最大流在在G(x)中寻找任何中寻找任何s-t 路径路径.s2453t4411213Ford-Fulkerson 最大流最大流判定路径的容量判定路径的容量 D.D.在路径上发送在路径上发送 D D 单位的流单位的流.更新剩余容量更新剩余容量.111212321s2453t5411213Ford-Fu
2、lkerson最大流最大流寻找任何寻找任何s-t 路径路径 111212321s2453t64211112211113Ford-Fulkerson 最大流最大流1111321s2453t判定路径的容量判定路径的容量 D D 在路径中发送在路径中发送 D D 单位的流单位的流.更新剩余网络更新剩余网络74211112211113Ford-Fulkerson 最大流最大流1111321s2453t寻找任何寻找任何 s-t 路径路径811111412112113Ford-Fulkerson 最大流最大流11321s2453t判定路径的容量判定路径的容量 D D 在路径中发送在路径中发送 D D 单位
3、的流单位的流.更新剩余网络更新剩余网络9111114121122113Ford-Fulkerson 最大流最大流11321s2453t寻找任何寻找任何 s-t 路径路径101112111142211221Ford-Fulkerson 最大流最大流11311s2453t2判定路径的容量判定路径的容量 D D 在路径中发送在路径中发送 D D 单位的流单位的流.更新剩余网络更新剩余网络11112111142211221Ford-Fulkerson 最大流最大流11311s2453t寻找任何寻找任何 s-t 路径路径2121111141311211322121Ford-Fulkerson 最大流最大流21s2453t2判定路径的容量判定路径的容量 D D 在路径中发送在路径中发送 D D 单位的流单位的流.更新剩余网络更新剩余网络131111141311211322121Ford-Fulkerson 最大流最大流21s2453t2在剩余网络中没有在剩余网络中没有 s-t 路径路径.此流是最优的此流是最优的.141111141311211322121Ford-Fulkerson 最大流最大流21s2453t2这些是从结点这些是从结点 s 可达的结点可达的结点.s245315Ford-Fulkerson 最大流最大流1122212s2453t这是最优流这是最优流.16