网络流算法专题[精选].ppt

费用流算法 求最小费用最大流的基本思想是贪心法。即：对于流f，每次选择最小费用可改进路进行改进，直到不存在可改进路为止。这样的得到的最大流必然是费用最小的。 算法可描述为： 第1步. 令f为零流。 第2步. 若无最小费用可改进路，转第5步；否则找到最小费用可改进路，设为P。 第3步. 根据P求delta（改进量）。 第4步. 放大f。转第2步。 第5步. 算法结束。此时的f即最小费用最大流。 如何求最小费用可改进路 设带费用的网络流图G = (V, E, C, W)，它的一个可行流是f。我们构造带权有向图B = (V’, E’)，其中： V’ = V。 若Vi, Vj∈E，fijCij，那么Vi, Vj∈E’，权为Wij。若Vi, Vj∈E，fij0，那么Vj, Vi∈E’，权为-Wij。 显然，B中从S到T的每一条道路都对应关于f的一条可改进路；反之，关于f的每条可改进路也能对应B中从S到T的一条路径。即两者存在一一映射的逻辑关系。 故若B中不存在从S到T的路径，则f必然没有可改进路；不然，B中从S到T的最短路径即为f的最小费用可改进路。 现在的问题变成：给定带权有向图B = (V’, E’)，求从S到T的一条最短路径。 迭代法求最短路经 考虑到图中存在权值为负数的弧，不能采用Dijkstra算法；Floyd算法的效率又不尽如人意——所以，这里采用一种折衷的算法：迭代法（bellman算法）。 设Short[i]表示从S到i顶点的最短路径长度；从S到顶点i的最短路径中，顶点i的前趋记为Last[i]。那么迭代算法描述如下：（为了便于描述，令n = |V’|，S的编号为0，T的编号为n+1） step 1. 令Short[i] ? +∞（1≤i≤n+1），Short[0] ? 0。 step 2. 遍历每一条弧Vi, Vj。若Short[i] + i, j Short[j]，则令Short[j] ? Short[i] + i, j，同时Last[j] ? i。重复做step 2直到不存在任何任何弧满足此条件为止。 step 3. 算法结束。若Short[n + 1]= +∞，则不存在从S到T的路径；否则可以根据Last记录的有关信息得到最短路径。 一次迭代算法的时间复杂度为O(kn2)，其中k是一个不大于n的变量。在费用流的求解过程中，k大部分情况下都远小于n。 procedure costflow; {求最小费用最大流} var i, j, x, delta : integer; best, last : tline; {best：最短路长度；last：可改进路中的前趋顶点} more : boolean; begin repeat fillword(best, sizeof(best) shr 1, maxint); fillchar(last, sizeof(last), 0); last[1] := maxint; best[1] := 0; {赋初值} repeat more := false; for i := 1 to n do if best[i] maxint then for j := 1 to n do begin if (flow[i, j] limit[i, j]) and (best[i] + cost[i, j] best[j]) then begin best[j] := best[i] + cost[i, j]; last[j] := i; more := true; end; if (flow[j, i] 0) and (best[i] - cost[j, i] best[j]) then begin best[j] := best[i] - cost[j, i]; last[j] := -i; more := true; end; end; until not more; {找最优可改进路} if best[n] = maxint then break; delta := maxint; i := n; repeat j := i; i := abs(last[j]);