首页 > 编程语言 > 详细

关于最短增广路算法和连续最短增广路算法的操作步骤

时间:2015-07-10 22:00:27      阅读:381      评论:0      收藏:0      [点我收藏+]

最短增广路算法(SAP):

1.初始化容量网络和网络流;

2.构造残留网络和层次网络,如果汇点不在层次网络中,则算法结束;

3.在层次网络中不断用BFS增广,直到层次网络中没有增广路为止;每次增广完毕,在层次网络中要去掉因改进流量而导致饱和的弧;

4.转到步骤(2)。

 

连续最短增广路算法(Dinic):

1.初始化容量网络和网络流;

2.构造残留网络和层次网络,如果汇点不在层次网络中,则算法结束;

3.在层次网络中用一次DFS过程进行增广,DFS执行完毕,该阶段的增广也执行完毕;

4.转到步骤(2)。

关于最短增广路算法和连续最短增广路算法的操作步骤

原文:http://www.cnblogs.com/zufezzt/p/4637180.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!