图论动画-圈消除算法

《图论动画-圈消除算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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环绕圈发送流沿着负代价圈发送流.12435202515这个圈的容量是15.形成

2、下一个剩余网络.6在剩余网络上的容量12435102052010102552010157在剩余网络上的代价124352267-7-2-2-1-4-6寻找负代价圈,如果存在一个的话.58环绕圈发送流12435沿着负代价圈发送流.圈的容量是10.形成下一个剩余网络.2020109在剩余网络上的容量1243510105201020251510151010在剩余网络中的代价12435122567-7-6-2-1-4寻找负代价圈,如果存在一个的话.11环绕圈发送流12435沿着负代价圈发送流.这个圈的容量是5.形成下一个剩余网络.1051

3、02012在剩余网络上的容量124355102551525151020105513在剩余网络中的代价124351227-7-6-2-1-44-25寻找负代价圈,如果存在一个的话.14环绕圈发送流沿着负代价圈发送流.这个圈的容量是5.形成下一个剩余网络.124351010515在剩余网络上的容量124355152552025205205516在剩余网络中的代价124351227-7-6-2-1-445寻找负代价圈,如果存在一个的话.没有负代价圈.但是证明是什么?17在剩余网络中计算最短距离124351227-7-6-2-1-445

4、令d(j)是从结点1到结点j的最短路径距离.下一步令p(j)=-d(j)07111210计算cp18在剩余网络中的即约代价12435071112100020-0400001在G(x*)中对最优流的即约代价都是非负的.19