求解网络最大流的标号法优化

求解网络最大流的标号法包括两个基本过程：标号过程与调整过程。

1.标号过程

标号过程的主要目的是寻找网络中的增广链。

开始时，总是先给vs标上（0，+∞）。标号中第一个数字0表示增广链的起点，第二个数字+∞表示增广链的流量调整量，由于现在是起点，其调整假设为+∞。这时，vs虽是标号的点，但是未检查点，网络中其余的点都是未标号点。一般地，取一个标号而未检查点vi，对所有未标号点vj。

（1）若在弧（vi，vj）上，fij＜Cij，则给vj标号（vi，l（vj））。标号的第一个数字表示vj的标号是由vi出发得到的，l（vj）表示目前为止增广链可调整的流量，其确定方法为

l（vj）=min｛l（vi），cij-fij｝

这样点vj就成为一个新的标号而未检查点。

（2）若在弧（vi，vj）上，fij＞Cij，则给vj标号（-vi，l（vj））。同样标号的第一个数字表示vj的标号是由vi反向出发得到的，l（vj）表示目前为止增广链可调整的流量，其确定方法为

l（vj）=min｛l（vi），fji｝

这样点vj就成为一个新的标号而未检查点。

重复上述步骤，一旦vt得到标号，表明找到了一条从vs到vt的增广链，转入下面的调整过程。若所有的标号都已检查过，而标号过程进行不下去时，则算法结束，这时的可行流就是网络的最大流。

2.调整过程

利用网络中各点的第一个标号，从vt出发，利用反向追踪的方法找出增广链μ。然后令

得到网络的新流量分布，再重复前述的标号过程。

例6.4.1（最大流的标号法）　利用标号法求图6.4.1所示网络的最大流，弧旁数字为（cij，fij）。

解　（1）标号过程1。

①首先，给vs标号（0，+∞）。

②检查vs点，从它出发可以给v1、v2、v3标号，任取一个，如给v1标（vs，6）。

③检查v1点，可以给v3、v4标号，任取一个，如给v3标（v1，1）。

④检查v3点，可以给v4、v5标号，任取一个，如给v5标（v3，1）。

⑤检查v5点，可以给v4、vt标号，任取一个，如给v4标（-v5，1）。

⑥检查v4点，只可以给vt标（v4，1）。

至此得到了网络中的一条增广链，如图6.4.2所示的双线，然后转入调整过程。

图6.4.2

（2）调整过程1。

根据标号过程得到的增广链vs→v1→v3→v5→v4→vt，确定流量调整量为l（vt）=1，对该增广链的前向弧增加流量，后向弧减少流量，得到如图6.4.3所示的新流量，当前网络的流量v（f）=10。

图6.4.3

（3）标号过程2。

①首先，给vs标号（0，+∞）。

②检查vs点，从它出发可以给v1、v2、v3标号，任取一个，如给v1标（vs，5）。

③检查v1点，只可以给v4标（v1，2）。

④检查v4点，可以给v5、vt标号，任取一个，如给vt标（v4，2）。

至此得到网络中的一条增广链，如图6.4.4所示的双线，然后第二次转入调整过程。

图6.4.4(www.xing528.com)

（4）调整过程2。

根据标号过程得到的增广链vs→v1→v4→vt，确定流量调整为l（vt）=2，由于该增广链中的弧均为前向弧，因此所有前向弧增加流量，得到如图6.4.5所示的新流量，当前网络的流量v（f）=12。

图6.4.5

（5）标号过程3。

①首先，给vs标号（0，+∞）。

②检查vs点，从它出发可以给v1、v2、v3标号，但若给v1标号后，无法继续标号，所以在v2、v3中任取一个，如给v2标（vs，1）。

③检查v2点，从它出发只能给v3标（v2，1）。

④检查v3点，从它出发可以给v1和v4标号，但与前述原因相同，若给v1标号后，无法继续标号，所以只能给v4标（v3，1）。

⑤检查v4点，从它出发可以给v5和vt标号，所以给vt标（v4，1）。

至此得到了网络中的一条增广链，如图6.4.6所示的双线，然后第三次转入调整过程。

图6.4.6

（6）调整过程3。

根据标号过程得到的增广链vs→v2→v3→v4→vt，确定流量调整为l（vt）=1，由于该增广链中的弧均为前向弧，因此所有前向弧增加流量，得到如图6.4.7所示的新流量，当前网络的流量v（f）=13。

图6.4.7

（7）标号过程4。

①首先，给vs标号（0，+∞）。

②检查vs点，给v3标（vs，1）。

③检查v3点，给v4标（v3，1）。

④检查v4点，给vt标（v4，1）。

至此得到网络中的一条增广链，如图6.4.8所示的双线，然后第四次转入调整过程。

图6.4.8

（8）调整过程4。

根据标号过程得到的增广链vs→v3→v4→vt，确定流量调整为l（vt）=1，由于该增广链中的弧均为前向弧，因此所有前向弧增加流量，得到如图6.4.9所示的新流量，当前网络的流量v（f）=14。

图6.4.9

（9）标号过程5。

①首先，给vs标号（0，+∞）。

②检查vs点，只能给v1标（vs，3）。

③检查v1点，不能给其他点标号。

至此已得到该网络的最大流量。而且此时网络中的点被分为两类：有标号的与无标号的，这两类点的划分正好可以得到网络的最小截集，如图6.4.10所示。

图6.4.10

上述过程就是利用标号法求解最大流的基本方法。需要注意的是，网络中弧的容量一旦给定，网络最大流量就是确定的，但在一般情况下，这些流量在弧上的分配可能是不同的。因为在寻找增广链的过程中有时存在着多条线路可供选择，选择不同得到的流量分布就会不同。