最大流问题的最短增广路径算法.ppt
( 4.5 )《最大流问题的最短增广路径算法.ppt》由会员分享，可在线阅读，更多相关《最大流问题的最短增广路径算法.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、最大流问题的最短增广路径算法34114212331s2453t这是初始网络和初始残留网络这是初始网络和初始残留网络.44114212331s2453t结点标号从此以后将是距离标号结点标号从此以后将是距离标号.054321t453s2d(j)是在是在G(f)中的中的j到到t的的最短的距离的的最短的距离02211154114212331s2453t弧弧(i,j)是是 可进入的可进入的，如果，如果 d(i)=d(j)+1.054321t453s2一条可进入弧的一条可进入弧的 s-t 路径是最短路径路径是最短路径.022111可进入弧将表示成粗线可进入弧将表示成粗线.6424241121331s245
2、3t使用可进入弧从使用可进入弧从 s 开始进行深度优先搜索开始进行深度优先搜索.054321t453s2022111下一步下一步.发送流并更新残留容量发送流并更新残留容量.210724 2241121331s2453t这里是更新后的残留容量这里是更新后的残留容量.054321t453s2022111如果需要，将在以后更新距离标号如果需要，将在以后更新距离标号824 2241121331s2453t054321t453s2022111使用可进入弧从使用可进入弧从 s 开始进行深度优先搜索开始进行深度优先搜索.下一步下一步.发送流并更新残留容量发送流并更新残留容量.21092224 2241113
3、11s2453t054321t453s2022111这里是更新后的残留容量这里是更新后的残留容量.如果需要，将在以后更新距离标号如果需要，将在以后更新距离标号102224 224111311s2453t054321t453s2022111使用可进入弧从使用可进入弧从 s 开始进行深度优先搜索开始进行深度优先搜索.21如果没有从如果没有从i出发的可进入弧，那么出发的可进入弧，那么relabel(i)且沿着到且沿着到 i 的的路径回溯路径回溯.112224 224111311s2453t054321t45s2022111使用可进入弧从使用可进入弧从 s 开始进行深度优先搜索开始进行深度优先搜索.2
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 最大 问题 增广 路径 算法
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
限制150内