标号算法方法技巧

标号算法方法技巧

关于求网络最大流和最小割的标号算法：
给定一个有向图G=(V,E)，把图中的边看作管道，每条边上有一个权值，表示该管道的流量上限。给定源点s和汇点t，现在假设在s处有一个水源，t处有一个蓄水池，问从s到t的最大水流量是多少。这就叫做网络流问题。用数学语言描述就是：
设G=(V,E)是一个流网络，设c(u, v)>＝0 表示从u到v的管道的流量上限。设s为源，t为汇。G的流是一个函数f: V×V →R，且满足下面三个特征：
1. 容量限制：对于所有的 u,v ∈ V, 要求f(u, v) <= c(u, v)
2. 斜对称性：对于所有的 u,v ∈ V, 要求f(u, v) = - f(v, u)
3. 流的会话：对于所有的 u ∈ V - {s, t}，要求∑f(u, v) = 0；v∈V
f(u,v)称为从结点u到v的网络流，它可以为正也可以为负。流 f 的值定义为：
|f| = ∑f(s, v)
v∈V
即从源出发的所有流的总和。
最大流问题就是找出给定流网络的最大流。网络流问题可以归结为一类特殊的线性规划问题。
寻找最大流的基本方法是Ford-Fulkerson方法，该方法有多种实现，其基本思想是从某个可行流F出发，找到关于这个流的一个可改进路经P，然后沿着P调整F，对新的可行流试图寻找关于他的可改进路经，如此反复直至求得最大流。现在要找最小费用的最大流，可以证明，若F是流量为V(F)的流中费用最小者，而P是关于F的所有可改进路中费用最小的可改进路，则沿着P去调整F,得到的可行流F'一定是流量为V(F')的所有可行流中的最小费用流。这样，当F是最大流时候，他就是所要求的最小费用最大流。
注意到每条边的单位流量费用B(i,j)≥0，所以F=0必是流量为0的最小费用流，这样总可以
从F=0出发求出最小费用最大流。一般的，设已知F是流量V(F)的最小费用流，余下的问题就是如何去寻找关于F的最小费用可改进路。为此我们将原网络中的每条弧<u,v>变成两条方向相反的弧：
1。前向弧<u,v>，容量C和费用B不变，流量F为0；
2。后向弧<v,u>，容量C为0，费用为-B，流量F为0；
每一个顶点上设置一个参数CT，表示源点至该顶点的通路上的费用和。如果我们得出一条关于F的最小费用可改进路时，则该路上的每一个顶点的CT值相对于其它可改进路来说是最小的。每一次寻找最小费用可改进路时前，源点的CT为0，其它顶点的CT为+∞。
设cost为流的运输费用，初始时由于F=0,则cost=0,我们每求出一条关于F的最小费用可改进路，则通过cost ← cost + ∑B(e)*d, （其中e∈P,d为P的可改进量）来累积流的运输费用
的增加量。显然，当求出最小费用最大流时，cost便成为最大流的运输费用了。
另外设置布尔变量break为最小费用可改进路的延伸标志，在搜索了网络中的每一个顶点后
，若break=true表示可改进路还可以延伸，还需要重新搜索网络中的顶点；否则说明最小费
用的可改进路已经找到或者最大流已经求出。
下面是算法的伪代码：
cost← 0;
repeat
可改进路撤空；
设源点的CT值为0并进入可改进路；
repeat
break← false;
for u ←1 to N do
begin
分析U出发的所有弧<U,V>;
if (<U,V>的流量可改进）and(源点至U有通路)and(U的CT值+<U,V>的费用 < V的CT值) then
begin
break← true;
V的CT值← U的CT值+<U,V>的费用；
V进入可改进路经并为之标号；
end if
end for
until break=false
if 汇点已标号 then
begin
从汇点出发倒向修正可改进路的流量；
cost ← cost + ∑B(e)*d（其中e∈P,d为P的可改进量）；
end if
until 汇点未标号；
可见，上述的算法和求最大流的Edmonds-Karp标号算法几乎一样，因为这两种算法都使用宽度优先搜索来来寻找增广路径，所以复杂度也相同，都是O(VE)，其中V是节点数目，E是边数目。