算法设计与分析 第2版 第9章-图算法设计.ppt

如果f是具有起点s和终点t的一个流，则以下条件是等价的： f是G的最大流。 残留网络Gf中不包含增广路径。 对G的某个割集(S,T)，有f(S,T)=c(S,T)。 9.4.4 求最小费用最大流 　　在给定的网络G=(V,E)中，对每条边(u,v)，除了给出其容量cu,v外，还给出单位流量的费用bu,v≥0。 　　当最大流不唯一时，在这些最大流中求一个f，使流f的总费用达到最小，这便是最小费用最大流问题。 　　例如n辆卡车要运送物品，从s地到t地，由于每条路段都有不同的路费要缴纳，每条路能容纳的车的数量有限制，最小费用最大流问题指如何分配卡车的出发路径可以达到费用最低，物品又能全部送到。 1. 求最小费用最大流的步骤 　　求最小费用最大流的方法之一是采用和前面介绍的最大流算法思路相类似，一般首先给出零流作为初始流。这个流的费用为零，当然是最小费用的。 　　然后寻找一条起点s至终点t的增广路径，但要求这条增广路径必须是所有增广路径中费用最小的一条。 　　如果能找出增广路径，则在增广路径上增流，得出新流。将这个流做为初始流看待，继续寻找增广路径增流。这样迭代下去，直至找不出增广路径，这时的流即为最小费用最大流。这一算法思路的特点是保持解的最优性（每次得到的新流都是费用最小的流），而逐渐向可行解靠近（直至最大流时才是一个可行解）。 采用这种迭代法求最小费用最大流的步骤如下： 　　1. 取k=0，f(0)=0，f(0)是零流中费用最小的流。 　　2. 构造一个赋权有向图W(f(k))，它的顶点与原来的网络G的顶点相同，但把G中的每一条边(i,j)变成两个方向相反的边(i,j)和(j,i)，两边的权分别为wi,j和wj,i： 　　3. 采用最短路径算法，在赋权有向图W(f(k))中找出起点s到终点t的最短路径，此时分为以下两种情况： 　　（1）若不存在最短路径，则f(k)就是最小费用最大流，算法结束。 　　（2）若存在最短路径，记为μ，则μ是原网络中的一个增广路径，在增广路径μ上对f(k)进行如下调整： 　　① 求增广路径μ上各边的最小值，得到 　　　　?=MIN{ 　　　　　　　}。 　　② 调整流量：只调整增广路径μ上各边的流量，其他边的流量不变。调整增广路径μ上各边流量的方式是：若边i,j∈μ+，则增大?；若边i,j∈μ-，则减少?。从而得到一个新的可行流f(k+1)。 　　4. 令k=k+1，转第2步。 【例9.4】 对于下图所示的网络，起点s=0，终点t=5，边i，j的权为c(i，j)，b(i，j)，其中c(i，j)表示容量，b(i，j)表示单位流量费用。给出求最小费用最大流的过程。 0 1 2 3 4 5 5,3 4,1 1,1 2,4 2,4 5,2 3,3 3,1 1,2 解：首先初始化最大流量maxf=0，最大流最小费用mincost=0，求maxf和mincost的过程如下： （1）k=0，取f(0)=0为初始可行流（即从零流开始调整）。 0 1 2 3 4 5 5,3 4,1 1,1 2,4 2,4 5,2 3,3 3,1 1,2 （2）构造一个赋权有向图W(f(0))如左图所示，求出其中从起点0到终点5的最短路径为0→1→3→5，由c、f求出该路径上的最小调整量?=3。将f(0)中f[3][5]调整为3，f[1][3]调整为3，f[0][1]调整为3，得到的f(1)如右图所示。 0 1 2 3 4 5 3 1 1 4 4 2 3 1 2 0 1 2 3 4 5 0 3 0 0 0 3 3 0 0 W(f(0)) f(1) 执行maxf+=?，求出maxf=3；执行mincost+=?*(w[0][1]+w[1][3]+w[3][5])=3*(1+3+2)=18，求出mincost=18。 （3）k=1，构造一个赋权有向图W(f(1))如左图所示，求出其中从起点0到终点5的最短路径为0→1→2→4→3→5，由c、f求出该路径上的最小调整量?=1。将f(1)中f[3][5]调整为4，f[4][3]调整为1，f[2][4]调整为1，f[1][2]调整为1，f[0][1]调整为4，得到的f(2)如右图所示。 0 1 2 3 4 5 3 1 1 4 4 2 -3 1 2 0 1 2 3 4 5 0 4 1 1 0 4 3 1 0 W(f(1)) f(2) -1 -2 执行maxf+=?，求出maxf=3+1=4；执行mincost+=?*(w[0][1]+w[1][2]+w[2][4]+w[4][3]+w[3][5])=1*(1+1+4+1+2)=18，求出mincost=27。 （4）k=2，构造一个赋权有向图W(f(2))如左图所示，求出其中从起点0到终点5的最短路径