上一次我们把求最大流的问题转化成了找到一条增广路然后优化的问题。今天讲讲怎么找增广路。
Ford-Fulkerson算法（标号法）求增广路。
标号法的流程分为标记和调整两个阶段。在标记阶段中，为图中的每个顶点找一个优化方案。在调整阶段，利用标记阶段的记号，重新分配流量。可以看出来，标记法的核心是第一个阶段，怎么为每个顶点找到一个优化方案呢？很简单，只需要两个量就记下每个点的优化方案了。一个数记录需要优化的弧连接的是哪个顶点，另一个数记录能够优化的量。
在标记过程，网络中的顶点可以分为三类：
① 未标号顶点；
② 已标号，未检查邻接顶点；
③ 已标号，且已检查邻接顶点。
标号过程开始时，总是先给Vs标上(0, +∞)，0表示Vs是汇点，+∞表示Vs可以流出任意多
的流量（先不讨论与之连接的弧能不能吸收这些流量）。这时Vs是已标号而末检查的顶点，其余都是末标号点。然后从源点Vs出发，使用广度优先搜索对它的每个邻接顶点进行标号。
假设已标号而未检查的顶点是u，对u的一个未标号顶点v：
a)若v与u“正向”邻接，且在弧上目前分配的流量f(u, v)＜弧的容量c(u, v)，则给v标号(u，L(v))，这里L(v)= min{ L(u), c(u, v)–f(u, v)}，L(u)是顶点u能提供的标号，c(u,v)–f(u, v)是弧能接受的标号，取二者中的较小者。这时顶点v成为已标号而末检查的顶点。
b)若v与u“反向”邻接，且在弧< v, u>上f(v, u)＞0，则给v标号( -u, L(v))，这里L(v) =min{L(u), f(v, u) }。这时顶点v成为已标号而未检查的顶点。
当u的全部邻接顶点都已检查后，u成为已标号且已检查过的顶点。
重复上述步骤直至标记到目的地点，若目的点可改进量α= 0，或者不能给目的点标号，则算法结束，这时的可行流即为最大流。算法结束。一旦目的点Vt被标号并且第2个分量大于0，则表明存在一条从Vs到Vt的增广路P，接下来要进入调整过程；
调整过程采用“倒向追踪”的方法，从Vt开始，利用标号顶点的第一个分量逐条弧地找出增广路P，并以Vt的第二个分量L(Vt)作为改进量α，改进P路上的流量。
网友评论