最大流算法

最大流算法

算法思想:最大流问题实际上是求一可行流{fij}，使得v(f达到最大。若给了一个可行流f，只要判断N中有无关于f的增广路径，如果有增广路径，改进f， 得到一个流量增大的新的可行流；如果没有增广路径，则得到最大流。
1.寻求最大流的标号法(Ford,Fulkerson)
    从一个可行流(一般取零流)开始，不断进行以下的标号过程与调整过程，直到找不到关于f的可增广路径为止。
    (1)标号过程
    在这个过程中，网络中的点分为已标号点和未标号点，已标号点又分为已检查和未检查两种。每个标号点的标号信息表示两个部分：第一标号表明它的标号从哪一点得到的，以便从vt开始反向追踪找出也增广路径；第二标号是为了表示该顶点是否已检查过。
    标号开始时，给vs标上(s，0)，这时vs是标号但末检查的点，其余都是未标号的点，记为(0，0)。
    取一个标号而未检查的点vi，对于一切未标号的点vj：
    A．对于弧(vi，vj)，若fij<cij，则给vj标号(vi，0)，这时，vj点成为标号而未检查的点。
    B．对于弧(vi，vj)，若fji>0，则给vj标号(-vi，0)，这时，vj点成为标号而未检查的点。
    于是vi成为标号且已检查的点，将它的第二个标号记为1。重复上述步骤，一旦vt被标上号，表明得到一条从vi到vt的增广路径p，转入调整过程。
    若所有标号都已检查过去，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。
    (2)调整过程
    从vt点开始，通过每个点的第一个标号，反向追踪，可找出增广路径P。例如设vt的第一标号为vk(或-vk)，则弧(vk，vt)(或相应地(vt，vk))是p上弧。接下来检查vk的第一标号，若为vi(或-vi)，则找到(vi，vk)(或相应地(vk，vi))。再检查vi的第一 标号，依此类推，直到vs为止。这时整个增广路径就找到了。在上述找增广路径的同时计算Q：
          Q=min{min(cij-fij)，minf*ij}
    对流f进行如下的修改：
    f'ij =  fij+Q   (vi，vj)∈P的前向弧的集合
    f'ij =  fij-Q   (vi，vj)∈P的后向弧的集合
    f'ij =  f*ij     (vi，vj)不属于P的集合
接着，清除所有标号，对新的可行流f’，重新进入标号过程。