文件名称：网络的最小费用最大流
文件大小：11KB
文件格式：TXT
更新时间：2013-06-29 07:08:15
图论 网络 最小费用 最大流
网络的最小费用最大流，弧旁的数字是容量(运费)。 一．Ford和Fulkerson迭加算法. 基本思路：把各条弧上单位流量的费用看成某种长度,用求解最短路问题的方法确定一条自V1至Vn的最短路;在将这条最短路作为可扩充路,用求解最大流问题的方法将其上的流量增至最大可能值;而这条最短路上的流量增加后,其上各条弧的单位流量的费用要重新确定,如此多次迭代,最终得到最小费用最大流. 迭加算法： 二．圈算法： 1) 利用Ford和Fulkson标号算法找出流量为F(<=最大流)的流f. 2) 构造f对应的调整容量的流网络N'(f). 3) 搜索N'(f)中的负费用有向图C(Floyd算法),若没有则停止,否则转(4). 4) 在C上找出最大的循环流,并加到N上去,同时修改N'(F)中C的容量,转(3).