3.最大流的一种算法——标号法

标号法是由 Ford 和 Fulkerson 在 1957 年提出的。用标号法寻求网络中最大流的基本思想是寻找可增广轨，使网络的流量得到增加，直到最大为止。即首先给出一个初始流，这样的流是存在的，例如零流。如果存在关于它的可增广轨，那么调整该轨上每条弧上的流量，就可以得到新的流。对于新的流，如果仍存在可增广轨，则用同样的方法使流的值增大，继续这个过程，直到网络中不存在关于新得到流的可增广轨为止，则该流就是所求的最大流。

这个方法分为以下两个过程：
A.标号过程：通过标号过程寻找一条可増广轨。
B.增流过程：沿着可増广轨增加网络的流量。

3.1.标号过程

1.给发点标号为。

2.若顶点已标号，则对所有未标号的邻接顶点按如下规则标号：

（1）若，且时，令，则给顶点标号为，若，则不给顶点标号。

笔者认为这一步的意思是对流量未达到容量的流进行标号。

(2)，且，令则给标号为，若，则不给标号。

力求让反向流量都为0。

3.不断重复步骤(2)直到收点被标号，或不再有顶点可以标号为止。当被标号时，表明存在一条从到的可増广轨，则转向下面的增流过程。如果点不能被标号，且不存在其他可以标号的顶点时，表明不存在从到的増广轨，算法结束，此时所得的流就是最大流。

只要标过号的顶点，都有待优化的流，都要放到下面的增流过程中进行优化。

3.2.增流过程

1.令。

从起点开始

2.若的标号，则

正向流，流量加满

若的标号，则

反向流，流量清空

3.若，则去掉全部标号，并回到标号过程。否则令，并回到增流过程2。

如果到了终点，则这条轨调整完成，返回标下一条轨，若没到终点，则以下一个起点开始继续增流。

3.3.程序设计具体步骤

对于每个节点，标号包括两部分信息

该节点在可能的增广路中的一个节点，以及沿该可能的增广路到该节点为止。可以增广的最大流量。

1.置初始可行流（如零流）；对节点标号，即令任意正值（如1）。
2.若，继续下一步；否则停止，已经得到最大流，结束。
3.取消所有节点的标号，即令，；令LIST ，对节点标号，即令充分大的正值。
4.如果LIST 且继续下一步，否则：

(1)如果已有标号（即），则找到了一条增増广路，沿该増广路对流进行増广（增广的流量即是，増广路可以根据pred方便地回溯得到），转到2。
(2)如果没有标号（即且），则停止，已得到最大流。

5.从中移走一个节点;寻找从节点出发的所有可能的増广弧；
(1)对非饱和前向弧，若节点没有标号（即），对进行标号，即令

并将加入中。
(2)对非空后向弧，若节点没有标号（即），对进行标号，即令

并将加入中。

3.4.举例

例1 计算最大流，弧上两个数字分别代表容量和当前流量。

例1题图

编写Matlab程序：

clc,clear
u(1,2)=1;u(1,3)=1;u(1,4)=2;u(2,3)=1;u(2,5)=2;
u(3,5)=1;u(4,3)=3;u(4,5)=3;
f(1,2)=1;f(1,3)=0;f(1,4)=1;f(2,3)=0;f(2,5)=1;
f(3,5)=1;f(4,3)=1;f(4,5)=0;
n=length(u);list=[];maxf(n)=1;
while maxf(n)>0
    maxf=zeros(1,n);pred=zeros(1,n);
    list=1;record=list;maxf(1)=inf;
    %list是未检查邻接点的标号点，record是已标号点
    while (~isempty(list))&(maxf(n)==0)
        flag=list(1);list(1)=[];
        label1= find(u(flag,:)-f(flag,:));
        label1=setdiff(label1,record);
        list=union(list,label1);
        pred(label1)=flag;
        maxf(label1)=min(maxf(flag),u(flag,label1)...
        -f(flag,label1));
        record=union(record,label1);
        label2=find(f(:,flag));
        label2=label2';
        label2=setdiff(label2,record);
        list=union(list,label2);
        pred(label2)=-flag;
        maxf(label2)=min(maxf(flag),f(label2,flag));
        record=union(record,label2);
    end
        if maxf(n)>0
            v2=n; v1=pred(v2);
            while v2~=1
            if v1>0
                f(v1,v2)=f(v1,v2)+maxf(n);
            else
                v1=abs(v1);
                f(v2,v1)=f(v2,v1)-maxf(n);
            end
        v2=v1; v1=pred(v2);
            end
    end
end
f

当然，最大流问题也可以从线性规划的角度解决：

例2 现需要将城市的石油通过管道运送到城市，中间有4个中转站和，城市与中转站的连接以及管道的容量如图所示，求从城市到的最大流。

例2图

提供两个版本的Lingo程序：

model:
sets:
nodes/s,1,2,3,4,t/;
arcs(nodes,nodes)/s 1,s 3,1 2,1 3,2 3,2 t,3 4,4 2,4 t/:c,f;
endsets
data:
c=8 7 9 5 2 5 9 6 10;
enddata
n=@size(nodes); !顶点的个数;
max=flow;
@for(nodes(i)|i #ne#1 #and# i #ne# n:
@sum(arcs(i,j):f(i,j))=@sum(arcs(j,i):f(j,i)));
@sum(arcs(i,j)|i #eq# 1:f(i,j))=flow;
@sum(arcs(i,j)|j #eq# n:f(i,j))=flow;
@for(arcs:@bnd(0,f,c));
end

model:
sets:
nodes/s,1,2,3,4,t/;
arcs(nodes,nodes):c,f;
endsets
data:
c=0;
@text('fdata.txt')=f;
enddata
calc:
c(1,2)=8;c(1,4)=7;
c(2,3)=9;c(2,4)=5;
c(3,4)=2;c(3,6)=5;
c(4,5)=9;c(5,3)=6;c(5,6)=10;
endcalc
n=@size(nodes); !顶点的个数;
max=flow;
@for(nodes(i)|i #ne#1 #and# i #ne# n:
@sum(nodes(j):f(i,j))=@sum(nodes(j):f(j,i)));
@sum(nodes(i):f(1,i))=flow;
@sum(nodes(i):f(i,n))=flow;
@for(arcs:@bnd(0,f,c));
end