使用标号算法(Ford-Fulkerson)解决最大流问题
4星 · 超过85%的资源 需积分: 39 86 浏览量
2013-06-18
12:28:59
上传
评论
收藏 59KB DOC 举报 
《运筹学通论》课程上机实验报告
课程名称： 年级： 上机实验成绩：
任课教师： 姓名： 专业：
上机实验名称： 学号： 上机实验日期：
上机实验编号： 组号： 上机实验时间：
一．实验目的
使用标号算法(Ford-Fulkerson)解决最大流问题。 其基本思想是从某个可行流 F 出发，
找到关于这个流的一个可改进路经 P，然后沿着 P 调整 F，对新的可行流试图寻找关于
他的可改进路经，如此反复直至求得最大流。
二．实验内容
1.标号过程
在这个过程中,网络中的点或者是标号点(又分为已检查和未检查两种),或者是未标
号点,每个标号点的标号包含两部分:第一个标号表明它的标号是从哪一点得到的,以便
找出增广链;第二个标号是为确定增广链的调整量 用的.
标号过程开始,总先給 Vs 标上(0, + ),这时 Vs 是标号而未检查过的点,其余都是未
标号的点.一般地,取一个标号而未检查的点 Vi, 对一切未标号的点 Vj:
(1).若在弧( Vi, Vj)上,Fij<Cij,则給 Vj 标号(Vi, l(Vj))。这里 l(Vj)=min[l(Vi),Cij-Fij].
这时点 Vj 成为标号而未检查的点.
(2) 若在弧( Vj, Vi)上,Fij>0, 则給 Vj 标号(-Vi,l(Vj)),这里 l(Vj)=min[l(Vi),Fij].这时点
Vj 成为标号而未检查的点.若所有标号都是已检查过的,而标号过程进行不下去时,则算
法结束,这时的可行流就是最大流.
2.调整过程
首先按 Vt 及其他点的第一个标号,利用”反向追踪”的办法,找出增广链 u. 例如设 Vt
的第一个标号为 Vk(-Vk) , 则弧(Vk,Vt)(Vt,Vk)是 u 上的弧. 接下来检查 Vk 的第一个
标号,若为 Vi (-Vi) , 则找出(Vi,Vk)(或相应的(Vk,Vi)).再检查的第一个标号,依此下去,
直到为止.这时被找出的弧就构成了增广链 u.
令调整量 θ 是 l(Vt),即 Vt 的第二个标号:
Fij﹢θ （vi
，
vj）∈u+
Fij= Fij﹣θ （vi
，
vj）∈u-
Fij （vi
，
vj） u
去掉所有的标号,对新的可行流 F’={Fij ‘},重新进入标号过程.
三．使用环境
资源评论
lolelixu2014-01-18觉得还行吧，可以学到东西的
