算法创新与实践论文

（1.3）；否则当????的所有出弧都考虑完毕时，把???? 记为已检查，转（1.1）； （1.3）（增广）从终点t 的标号 ??，???? 逆向追踪找到增广路P，把路上 的每条弧的流量都增加????；去掉所有顶点上的标号，返回（1.0）；

??（1.4）（结束）网络已不再存在正向增广路，当前流????就是初始饱和流解。 ??（S2）用广探法对初始饱和流????寻找改进链。步骤基本用（S1）。不同之

处是在进行检查和标号的第三步时，除了检查点????的出弧之外还要考虑???? 点的一切入弧（??1，????），如果??1已标号，什么也不做；否则对??1 进行标号。设???? 的标号为 ??，???? ，当fli>0 时，令??1=min?[????，??1??]标??1 为 ???，??1 ，且将??1记为“已标号未检查”，然后继续选检查点进行检查和标号。当终点t 获得标号时，说明找到了一条改进链。在此改进链上，将正向弧的流量增加????，将反向弧中的

11流量减????，得到了新的饱和流????，返回开始步骤再找????改进链。当标号过程达不

到终点t 时，说明不再存在改进链，这时的饱和流即为最大流。

3.3 表格算法

（1）给网络一任意可行流（一般是零流）。 （2）寻找一条增流链P，画出表1。

表1 中??′ 表示标号的点，V\表示未获标号的邻点，Δ 表示流量可增值，?=min?{???，?????}。???为先行顶点???? 的流量可增值，????? 为弧 ????，???? 的流量可增值。如果弧 ????，??{???，?????}；如?? 为正向弧，且?????=?????????????>0此时取?=min?果弧 ????，??{???，??????}。；如果?????=0（不?? 为反向弧，且??????>0，此时取?=min?管????与????之间是正向弧还是反向弧），这时不给予???? 标号。

假如不出现?????=0 的情形，则??′ 中增加一个顶点。继续上述过程， 直至V\中包含终点，这时就找到了一条由起始点到终点的增流链，然后进入下一个步骤；假如检查??′中所有顶点的未标号的相邻顶点后，均不能使V\中的任一个顶点获得标号，则不存在流量可增链，此时网络中的可行流就是所求的最大流。 (3) 表1V\中，从终点反向追踪其先行顶点，再反向追踪下一个先行

4

算法创新与实践论文

顶点，直到起始点，就找到了一条增流链P，终点Δ 给出了增流链P的流量调整值，该链上各个弧调整后的流量为

??????=

调整后得到一个新的可行流，再进入步骤（2），直到不存在流量可增链为止。此时，将各条增流链上的流量调整值汇总就获得了最大流。

??????+?，对??上的正向弧????????，对??上的反向弧

3.4 数值算法

给定典则型运输网络D，设f 是D 的可行流。构造一个赋权有向图 W（f），定义W（f）中弧的权??????为：

?????? 当??????>0 ????????= = ????

+∞ 当??????=??????+∞ 当??????=0

典则型运输网络D 中求最小费用最大流的算法??6 如下： step1（准备）写出D 的容量矩阵C= ?????? 令

??????? ??,??=1,2,?,?? 。

step2（构造W（f）的权关联矩阵W）令i：=1。 step3 令j：=1。

step4 如果i≠1，转step5；否则令???????0，转step8。

step5 如果??????，则D 中弧（i，j）存在，转step6；否则令???????+∞，转 step8。

step6 如果??????0，令??????????????；否则令???????+∞，。 step8 如果j≠n，令j：=j+1，转step4；否则转step9。 step9 如果i≠n，令i：=i+1，转step3；否则转step10。

step10（计算W（f）的任意两顶点间的最短路的长）令??????：=??????，?????????，（i,j=1,2,?,n）,k：=1。

step11 对1≤i，j≤n。如果??????>??????+??????，则令??????：=??????+??????，

5

??×??

?????? 当??????

和费用矩阵B= ??????

??×??

和，

算法创新与实践论文

??????：=??????；否则

??????、?????? 保持不变

step12 如果k=n，转step13；否则，令k：=k+1，转step11。 step13（判定D 中是否存在关于f 的最小费用增广链）如果??????=+∞ ，则D 中不存在关于f 的最小费用增广链，转step22；否则令1：=s， r：=??????。转step14。

step14（求调整量θ）如果??1??>0，令θ=??1?????1??；否则令θ=????1。 step15 如果r=t，转step19；否则令1：=r，r：=??????。 step16 如果??1??>0 且θ>??1?????1??，令θ=??1?????1??。 step17 如果??1??=0 且θ>????1，令θ：=??r1。 step18 转step15。

step19（调整）令1：=s，r：=??????。

step20 如果??1??>0，令??1??：=??1??+??；否则令??1??：=??1?????。 step21 如果r=t，转step2；否则令1：=r，r：=??????，转step20。 step22（输出D 的最小费用最大流在所有弧的对应流量）令i：=1。 step23 令j：=1。

step24 如果i≠j 且??????>0，则D 中弧（i，j）存在，输出弧（i，j）和它的流量??????。

step25 如果j

3.5“构造式”算法

具体步骤描述如下：

step1 初始化构造图，各节点间流量置0；

step2 以当前节点V（初始时为源点S）为发点，寻找与其相邻的某 条边，使其满足（1）盈余最大且为正数；（2）该边的下一节点为非满载 点；

step3 若存在满足要求的边，则比较当前流量与该边盈余量折大 小，然后继续执行下一步；若不存在满足要求的边，则跳转至step8； step4 若当前流量小于或等于该边盈余量，则更新构造图（添加边 等相关信息），存储相关数据；若当前流量大于该边盈余量，则在该点标

6

算法创新与实践论文

记过流量后将大小等于该边盈余量的支流转step4 执行； step5 若未到汇点T，则返回step2；

step6（否则）沿原路径返回，检查路径上的每个节点；

step7 若发现某节点V 有过流量标记，则以该点为当前点；若退至 源点S（该路径无节点有过流量标记），则以源点S 为当前点。返回 step2；

step8 若当前点为源点S，则跳转至step9；若当前点非源点（即任 一中间点），将该边的流退回，并将该边标记为满载边，然后跳转至 step6；

step9 计算所有以源点S 为发点的边的流量和，得到最大流。算法结束。

3.6 一种改进算法（断路法）

假设网络初始可行流为零流，即使已给定别的初始可行流，也可退到零流，因为这不影响以后所求的最大流的值。在此基础上按以下

步骤操作：

第一步，找一条以发点V1 为起点以收点Vn 为终点且中间点较少的路，若这条路上有后向弧，则弃之另找。因此，约定找的路上仅含有前向弧，这样的路总是可以找到的，否则网络上的最大流量就是零流。

第二步，比较所找出的路中弧的容量，设其各弧容量的最小值为??????，则令此路上各弧的流量均增加??????，这时对应容量为最小值??????的弧??????上有流量等于容量，则称此弧为满值弧，在这满值弧上划“×”，表示此路已断，下次不可再走。

第三步，观察已找到的第一条弧是否满值，若未满值，即其容量大于已有流量，余容量不为零时，则考虑接此弧后是否还可以找到通往收点Vn 的同向路，若可找到，则按第二步操作；若找不到，表示此条弧流量已达最大。以后，则重复第一步到第三步的操作，在这过程中如果有的弧上流量不为0，则该弧的容量应理解为余容量；直到图中由V1 到Vn 的同向路都被“×”断掉，则这时最大流就是以V1 为起点的各条路上的第一条弧的各流量之和。

7