《(精品)图论动画-圈消除算法.ppt》由会员分享，可在线阅读，更多相关《(精品)图论动画-圈消除算法.ppt（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、15.082 和和 6.855J圈消除算法圈消除算法最小代价流问题最小代价流问题1243510,$420,$120,$225,$225,$520,$630,$725000-252初始容量和可行流初始容量和可行流1243510,1020,2020,1025,525,1520,030,2525000-25通过解决最大流，通过解决最大流，可以找到可行流可以找到可行流.3在剩余网络上的容量在剩余网络上的容量12435102020525101015520104在剩余网络上的代价在剩余网络上的代价124352267-7-5-2-2-1-45寻找负代价圈寻找负代价圈,如果如果存在一个的话存在一个的话.5环绕
2、圈发送流环绕圈发送流沿着负代价圈沿着负代价圈发送流发送流.12435202515这个圈的容量这个圈的容量是是15.形成下一个剩余网络形成下一个剩余网络.6在剩余网络上的容量在剩余网络上的容量12435102052010102552010157在剩余网络上的代价在剩余网络上的代价124352267-7-2-2-1-4-6寻找负代价圈寻找负代价圈,如果如果存在一个的话存在一个的话.58环绕圈发送流环绕圈发送流12435沿着负代价圈沿着负代价圈发送流发送流.圈的容量是圈的容量是10.形成下一个剩余网络形成下一个剩余网络.2020109在剩余网络上的容量在剩余网络上的容量124351010520102
3、0251510151010在剩余网络中的代价在剩余网络中的代价12435122567-7-6-2-1-4寻找负代价圈寻找负代价圈,如果如果存在一个的话存在一个的话.11环绕圈发送流环绕圈发送流12435沿着负代价圈沿着负代价圈发送流发送流.这个圈的容量这个圈的容量是是 5.形成下一个剩余网络形成下一个剩余网络.105102012在剩余网络上的容量在剩余网络上的容量124355102551525151020105513在剩余网络中的代价在剩余网络中的代价124351227-7-6-2-1-44-25寻找负代价圈寻找负代价圈,如果如果存在一个的话存在一个的话.14环绕圈发送流环绕圈发送流沿着负代价
4、圈沿着负代价圈发送流发送流.这个圈的容量这个圈的容量是是 5.形成下一个剩余网络形成下一个剩余网络.124351010515在剩余网络上的容量在剩余网络上的容量124355152552025205205516在剩余网络中的代价在剩余网络中的代价124351227-7-6-2-1-445寻找负代价圈寻找负代价圈,如果如果存在一个的话存在一个的话.没有负代价圈没有负代价圈.但是证明是什么但是证明是什么?17在剩余网络中计算最短距离在剩余网络中计算最短距离124351227-7-6-2-1-445令令 d(j)是从结点是从结点 1到结点到结点 j的最短路径的最短路径距离距离.下一步下一步 令令 p p(j)=-d(j)07111210计算计算cp p18在剩余网络中的即约代价在剩余网络中的即约代价12435071112100020-0400001在在G(x*)中对最优流中对最优流的即约代价都是非的即约代价都是非负的负的.19