数学建模-图论模型-图论.doc

图论算法1 最小生成树 11 生成树的概念 设图G(V，E)是一个连通图，当从图中任一顶点出发遍历图G时，将边集E(G)分成两个集合A(G)和B(G)。其中A(G)是遍历图时所经过的边的集合，B(G)是遍历图时未经过的边的集合。显然，G1(V，A)是图G的子图，则称子图G1是连通图G的生成树。图的生成树不是惟一的。如对图1(a)，当按深度和广度优先搜索法进行遍历就可以得到图1中(b)和(c)的两棵不同的生成树，并分别称之为深度优先生成树和广度优先生成树。 对于有n个顶点的连通图，至少有n-1条边，而生成树中恰好有n-1条边，所以连通图的生成树是该图的极小连通子图。若图G的生成树中任意加一条边属于边集B(G)中的边，则必然形成回路。 求解生成树在许多领域有实际意义。例如，对于供电线路或煤气管道的铺设问题，即假设要把n个城市联成一个供电或煤气管道网络，则需要铺设n1条线路。任意两城市间可铺设一条线路，n个城市间最多可能铺设n(n1)/2条线路，各条线路的造价一般是不同的。一个很实际的问题就是如何在这些可能的线路中选择n-1条使该网络的建造费用最少，这就是下面要讨论的最小生成树问题。 1.2 网的最小生成树 在前面我们已经给出图的生成树的概念。这里来讨论生成树的应用。 假设，要在n个居民点之间敷设煤气管道。由于，在每一个居民点与其余n1个居民点之间都可能敷设煤气管道。因此，在n个居民点之间，最多可能敷设n(n-1)/2条煤气管道。然而，连通n个居民点之间的管道网络，最少需要n-1条管道。也就是说，只需要n-1条管道线路就可以把n个居民点间的煤气管道连通。另外，还需进一步考虑敷设每一条管道要付出的经济代价。这就提出了一个优选问题。即如何在n(n-1)/2条可能的线路中优选n-1条线路，构成一个煤气管道网络，从而既能连通n个居民点，又能使总的花费代价最小。 解决上述问题的数学模型就是求图中网的最小生成树问题。把居民点看作图的顶点，把居民点之间的煤气管道看作边，而把敷设各条线路的代价当作权赋给相应的边。这样，便构成一个带权的图，即网。对于一个有n个顶点的网可以生成许多互不相同的生成树，每一棵生成树都是一个可行的敷设方案。现在的问题是应寻求一棵所有边的权总和为最小的生成树。 如何构造这种网的最小生成树呢?下面给出这样一种解法： (1)已知一个网，将网中的边按其权值由小到大的次序顺序选取。 (2)若选某边后不形成回路，则将其保留作为树的一条边；若选某边后形成回路，则将其舍弃，以后也不再考虑。 (3)如此依次进行，直到选够(n-1)条边即得到最小生成树。 现以图2为例说明此算法。设此图是用边集数组EV表示的，且数组中各边是按权值由小到大的次序排列，如下表所示。 k12345678910EVk.p12242651115EVk.p23436475626COSTEVk.p1,EVk.p2561011141819212733 按权值由小到大选取各边就是在数组中按下标k由1到en(图中边数)的次序选取。选前2条边(2，3)，(2，4)时均无问题，保留作为树的边；到第3条边(4，3)时将与已保留的边形成回路，将其舍去；同样继续做：保留(2， 6)；舍去(6，4)；保留(5，7)，(1，5)，(1，6)，此时，保留的边数已够(n-1)=6条边，此时必定将7个顶点全部互相连通了，后面剩下的边(1，2)，(5，6)就不必再考虑了。最后得到的最小生成树如图2a中深色边所示，其各边权值总和等于80。由离散数学中的图论可以证明，这就是最小生成树了，其权值最小。当图中有权值相等的边时，其最小生成树可能有不同的选取方案。 实现此算法的关键是，在选取某条边时应判断是否与已保留的边形成回路。 这可用将各顶点划分为集合的办法解决：假设数组tag(1.en)作为顶点集合划分的标志初值为0。在算法的执行过程中，当所选顶点u，v是连通的，则将相应位置的tagu，tagv置以相同的数字，而不连通的点在初期分属不同的集合，置不同的数字；一旦两个不同的连通分支连通了，则修改tag的值，将新的连通分支改为相同的数字。我们以图2为例。首先选(2，3)(2，4)边，由于是连通的，并且不出现回路。tag2:1，tag3:=tag4:=1是同一个集合 A；选(6，2)边与A集合连通；tag6:=1；再选(5，7)与集合A不连通，tag5: tag7:2构成另一集合B；选(1，5)边与集合B连通，tag 1:=2；此时，集合A 2，3，4，6；集合B5，7，1；当选(1，6)边时，(1，6)与集合A、集合B都连通，并且两个顶点分别属于两个不同的集合A、B，这使得集合A与集合B通过边(1，6)连通。修改集合B中tag的值，置为1，即将集合B并入集合A。边为n-1条，这就是一棵最小生成树。 根据集合标志数组tag的变化过程，很容易判断，选择一条新的边是否构成回路。当新选边的两个顶点u、v，若tagu和tagv相同并且均不等于0时，即u，v已在生成树集合中被保留过，加入u，v后即形成回路，不能选。而当tag utagv或者tagutagv0时，可以选并且不形成回路，说明u，v中至少有一个顶点未被选过或者被选过的u、v分别属于两个不同的集合，此时选择u，v可以将含u的集合与含v的集合连通，修改tag数组。如此下去，到所有顶点均已属于一个集合时，此最小生成树就完全构成了。 网的最小生成树算法描述如下： 假设算法中用到的数据结构是经过处理的。 COST(1.n，1.n)是带权数组存放网中顶点之间的权。EV(1.n*(n-1/2)按权从小到大存放排序后的顶点对，即EVK.P1存放一个顶点，边的另一顶点存放在EVK.P2之中。 tag(1.n)：顶点集合划分标志的数组。 Enumb：当前生成树的边数。 SM：当前权累计和。 PROC minspanningtree(VAR cost；VAR ev)； Var tag； BEGIN CALL INITIAL(tag); Enumb：0；SM:=0; 诸参量初始化 k:=1; 边数累计 WHILE (Enumb=n-1) AND (kn) DO Begin U:=EVk.P1；V:=EVk.P2； 选一对顶点(U，V) CALL FIND(U，T)； 找到含顶点U的集合T CALL FIND(V，W)； 找到含顶点V的集合W IF (TW) THEN Begin write(u，v)；Enumb:=Enumb+1； 最小生成树增加一条边 SM:=SM+COSTu，v； MERGE(T，W)；选u，v不会形成环，合并T，W集合，并修改tag end K:=K+1; 找下一条边 end IF Enumbw表示从城市v到城市W的航线，弧Vw上的标号代表从V城飞到w城所需要的时间。要寻找由该航空图上一给定城市到另一城市所需要的最短飞行时间。可以用求解这个有向图的单源最短路径算法来完成。 下面，我们讨论求解单源最短路径问题的贪心算法，也称Dijkstra算法。 设有向图G=(V，E)，其中，V=1，2，n)cost是表示G的邻接矩阵，costi，j表示有向边(i，j)的权。若不存在有向边(i，j)，则costi，j的权为无限大(oo)。令S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。 (1)令顶点V0为源点，集合S的初态只包含顶点V0，即S=V0。数组dist记录从源点到其他各顶点当前的最短距离，其初值为disti:=costv0，i，(i=2，n)。 (2)从S之外的顶点集合V-S中选出一个顶点W，使distW的值最小。于是，从源点到达W只通过S中的顶点，我们把W加入集合S。 (3)调整dist中记录的从源点到V-S中每个顶点V的距离：从原来的distv和distw+costw，v中选择较小的值作为新的distv。 (4)重复上述过程(2)和（3），直到S中包含V的全部顶点。 最终数组dist记录了从源点到V中其余各顶点的最短路径。 对图3所示的加权有向图应用Dijkstra算法，从源点V2出发到达各顶点的最短路径如下表所示。 最短路径 - 源点 中间顶点 终止顶点 长度 2 5 10 3 15 3 4 30 3 1 35 6 oo - 对图3的执行过程：初始时，S2，dist1oo，dist315，dist4oo，dist510，dist6oo，第一遍处理时，W2使dist5最小、于是把5加入S。然后，调整dist中从源点到其余各顶点的距离：dist315，为次小，将3加入S。dist4cost2，3+cost3，4=15+1530，经中间点3。S2，5，3，4，同理，dist1cost2，3+cost3，135，S2，5，3，4，1，由于2没有一条到6的路径，所以dist6=oo。 由此我们给出最短路径算法如下PROC shortpath(VAR cost；VAR dist；VAR path；VAR S，V0)；BEGIN FOR W:=1 TO n DO Begin distW:=costV0，W;最短路径初始化值 IF costV0，Wmax THEN pathW:=V0；path记载当前最短路径 End; S:=V0;Vnum:=1；到达点集合S和到达点S个数初值 WHILE (Vnumn-1) DO 最后一点已无选择余地 Begin Wm:=max；u:=V0; FOR W:=1 TO n DO IF(NOT W IN S) AND (distWWm) THEN Begin U:=W；Wm:=distw End; 找最小distw S:=S+U;Vnum:=Vnum+1; U为找到最短路径的终点 FOR W:=1 TO n DO IF (NOT W IN S) AND (distU+costU，WdistW) THEN Begin distW:=distU+costU，W; 调整非S集各点最短路径值 pathW:=U； 调整非S集各点最短路径 End; Vnum:=Vnum+1 End;END；PROC PRINTPATH(VAR dist VAR path；VAR S；V0)BEGIN FOR i:=1 TO n DO IF(i IN S) THEN Begin k:=i; WHILE (kV0) DO Begin write(k)；k:=pathk End; 通过找前趋点，反向输出最短路径 write(k)；writeln(disti) End; ELSE Begin write(i，V0)；writeln(max) End;END；容易看出，算法short path的时间复杂度为O(n2)，空间复杂度为O(n)。 3 拓扑排序本节说明了如何用深度优先搜索，对一个有向无回路图进行拓扑排序。有向无回路图又称为dag。对这种有向无回路图的拓扑排序的结果为该图所有顶点的一个线性序列，满足如果G包含(u,v)，则在序列中u出现在v之前（如果图是有回路的就不可能存在这样的线性序列)。一个图的拓扑排序可以看成是图的所有顶点沿水平线排成的一个序列，使得所有的有向边均从左指向右。因此，拓扑排序不同于通常意义上对于线性表的排序。有向无回路图经常用于说明事件发生的先后次序，图1给出一个实例说明早晨穿衣的过程。必须先穿某一衣物才能再穿其他衣物(如先穿袜子后穿鞋)，也有一些衣物可以按任意次序穿戴(如袜子和短裤)。图1(a)所示的图中的有向边(u,v)表明衣服u必须先于衣服v穿戴。因此该图的拓扑排序给出了一个穿衣的顺序。每个顶点旁标的是发现时刻与完成时刻。图1(b)说明对该图进行拓扑排序后将沿水平线方向形成一个顶点序列，使得图中所有有向边均从左指向右。下列简单算法可以对一个有向无回路图进行拓扑排序。procedure Topological_Sort(G);begin 1.调用DFS(G)计算每个顶点的完成时间fv; 2.当每个顶点完成后，把它插入链表前端; 3.返回由顶点组成的链表;end;图1(b)说明经拓扑排序的结点以与其完成时刻相反的顺序出现。因为深度优先搜索的运行时间为(V+E)，每一个v中结点插入链表需占用的时间为(1)，因此进行拓扑排序的运行时间(V+E)。图1 早晨穿衣的过程为了证明算法的正确性，我们运用了下面有关有向无回路图的重要引理。引理1有向图G无回路当且仅当对G进行深度优先搜索没有得到反向边。证明：假设有一条反向边(u,v)，那么在深度优先森林中结点v必为结点u的祖先，因此G中从v到u必存在一通路，这一通路和边(u,v)构成一个回路。：假设G中包含一回路C，我们证明对G的深度优先搜索将产生一条反向边。设v是回路C中第一个被发现的结点且边(u,v)是C中的优先边，在时刻dv从v到u存在一条由白色结点组成的通路，根据白色路径定理可知在深度优先森林中结点u必是结点v的后裔，因而(u,v)是一条反向边。(证毕)定理1Topological_Sort(G)算法可产生有向无回路图G的拓扑排序。证明:假设对一已知有问无回路图G=(V,E)运行过程DFS以确定其结点的完成时刻。那么只要证明对任一对不同结点u,vV，若G中存在一条从u到v的有向边，则fvfu即可。考虑过程DFS(G)所探寻的任何边(u,v)，当探寻到该边时，结点v不可能为灰色，否则v将成为u的祖先，(u,v)将是一条反向边，和引理1矛盾。因此，v必定是白色或黑色结点。若v是白色，它就成为u的后裔，因此fvfu。若v是黑色，同样fvfu。这样一来对于图中任意边(u,v)，都有fvfu，从而定理得证。（证毕）另一种拓扑排序的算法基于以下思想：首先选择一个无前驱的顶点（即入度为0的顶点，图中至少应有一个这样的顶点，否则肯定存在回路），然后从图中移去该顶点以及由他发出的所有有向边，如果图中还存在无前驱的顶点，则重复上述操作，直到操作无法进行。如果图不为空，说明图中存在回路，无法进行拓扑排序；否则移出的顶点的顺序就是对该图的一个拓扑排序。下面是该算法的具体实现：procedure Topological_Sort_II(G);begin 1 for 每个顶点uVG do du0; /初始化du,du用来记录顶点u的入度2 for 每个顶点uVG do3 for 每个顶点vAdju do dvdv+1; /统计每个顶点的入度4 CreateStack(s); /建立一个堆栈s5 for 每个顶点uVG do 6 if du=0 then push(u,s); /将度为0的顶点压入堆栈7 count0;8 while (not Empty(s) do begin9 utop(s); /取出栈顶元素10 pop(s); /弹出一个栈顶元素11 countcount+1;12 Rcountu; /线性表R用来记录拓扑排序的结果13 for 每个顶点vAdju do /对于每个和u相邻的节点v begin14 dvdv-1;15 if dv=0 then push(v,s); /如果出现入度为0的顶点将其压入栈 end; end; 16 if countG.size then writeln(Error! The graph has cycle.)17 else 按次序输出R;end;上面的算法中利用du来记录顶点u的入度，第2-3行用来统计所有顶点的入度，第5-6行将入度为0的顶点压入堆栈，第8-15行不断地从栈顶取出顶点，将该顶点输出到拓扑序列中，并将所有与该顶点相邻的顶点的入度减1，如果某个顶点的入度减至0，则压入堆栈，重复该过程直到堆栈空了为止。显而易见该算法的复杂度为O(VE)，因为第2-3行的复杂性就是O(VE)，后面8-15行的复杂性也是O(VE)。这个算法虽然简单，但是没有前面一个算法的效率高。4 网络流算法：概念在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立个网络流模型，然后用最大流算法高效地解决问题。 问题描述如图4-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到v4。现在要求制定一个运输方案使从v1到v4的产品数量最多。 图 4 - 1 图 4 - 2一、基本概念及相关定理 1)网络与网络流 定义1 给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点，对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图4-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。 所谓网络上的流，是指定义在弧集合E上一个函数f=f(vi，vj)，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图4-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。2)可行流与最大流 在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有： 定义2 满足下列条件 (1)容量约束：0fijcij，(vi,vj)E， (2)守恒条件 对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量vs(f)=汇点的净流入量（-vt(f)）的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。 网络N中流值最大的流f*称为N的最大流。3)可增广路径 所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。 定义3 设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件： (1)在p上的所有前向弧(vivj)都是非饱和弧，即0fijcij (2)在p上的所有后向弧(vivj)都是非零弧，即00，再令： f*ij = f*ij+Q (vi，vj) P的前向弧的集合 f*ij = f*ij-Q (vi，vj) P的后向弧的集合 f*ij = f*ij (vi，vj)不属于P的集合不难证明f*ij是可行流，且v(f*)=v(f*)+Qv(f*)。这与f*是最大流假设矛盾，必要性证毕。 证明 充分性：设N中不存在关于f*的增广路径，证明f*是最大流。我们利用下面的方法来定义A*。 令vs A* 若vi A*，且fij0，则令vj A*。因为不存在关于f*的增广路径，故vt不属于A*。 记A*-=V-A*，于是得到一个割(A*，A*-)，显然有 f*ij=cij，(vi，vj)(A*，A*-) f*ij=0，(vi，vj)(A*-，A*)所以v(f*)=c(A*，A*-)。于是f*必是最大流，定理得证。 由上述证明中可得，若f*是最大流，则网络中必存在一个割集c(A*，A*-)，使得v(f*)=c(A*，A*-)。 于是有以下重要定理。 定理2 最大流最小割定理：在一个网络N中，从vs到vt最大流的容量等于分离vs，vt的最小割的容量。二最大网络流 最大流问题实际上是求一可行流fij，使得v(f达到最大。定理1中证明实际上已为我们提供了寻求网络中最大流的一个方 法。若给了一个可行流f，只要判断N中有无关于f的增广路径，如果有增广路径，则按定理1的必要性证明中的办法，改进f， 得到一个沈量增大的新的可行流；如果没有增广路径，则得到最大流。而利用定理1充分性证明中定义A*的办法，可以根据vt是 否属于A*来判断N中有无关于f的增广路径。 下面我们用顶点标号法来定义A*，在标号过程中，有标号的顶点表示是A*中的点，没有标号的点表示不是A*中的点。如 果vt有标号，则说明找到了一条增广路径；如果标号过程进行不下去，而vt又还没有标号，则说明不存在增广路径，于是得到了最大流，同时也得到了一个最小割集。 1)寻求最大流的标号法(Ford,Fulkerson) 从一个可行流(一般取零流)开始，不断进行以下的标号过程与调整过程，直到找不到关于f的可增广路径为止。 (1)标号过程 在这个过程中，网络中的点分为已标号点和未标号点，已标号点又分为已检查和未检查两种。每个标号点的标号信息表示两个 部分：第一标号表明它的标号从哪一点得到的，以便从vt开始反向追踪找出也增广路径；第二标号是为了表示该顶点是否已检查过。 标号开始时，给vs标上(s，0)，这时vs是标号但末检查的点，其余都是未标号的点，记为(0，0)。 取一个标号而未检查的点vi，对于一切未标号的点vj： A对于弧(vi，vj)，若fij0，则给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=minmin(cij-fij)，minf*ij 对流f进行如下的修改： fij = fij+Q (vi，vj) P的前向弧的集合 fij = fij-Q (vi，vj) P的后向弧的集合 fij = f*ij (vi，vj)不属于P的集合接着，清除所有标号，对新的可行流f，重新进入标号过程。 2)求最大流标号法的具体实现 (1)数据结构 对于网络N，它首先是一个有向图N(V，E)，对于有向图一般我们用邻接矩阵表示，为了存放流f，这个有向图的弧上信息包含两个部分，分别是弧的容量与弧上的流。具体的数据结构如下： type nettype=record c，f：integer； end； var g：arrayO.maxn,O.maxn of nettype； 为了找到增广路径，我们要有对每个的顶点标号，第一个标号L表明它的标号从哪一点得到的，第二标号p是为了表示该顶点是否已检查过。具体数据结构如下： type nodetype=record l，p：integer； end； var Lt：arrayO.maxn of nodetype； (2)参考程序Program Max_Stream;Const Maxn=20;type nettype=record C,F:integer; end; nodetype=record L,P:integer; end;var Lt:arrayO.maxn of nodetype; G:Array0.Maxn,0.Maxn of Nettype; N,S,T:integer; F:Text; Procedure Init;初始化过程，读人有向图，并设置流为0Var Fn :String; I,J :Integer;Begin Write( Graph File = ); Readln(Fn); Assign(F,Fn); Reset(F); Readln(F,N); Fillchar(G,Sizeof(G) ,0); Fillchar(Lt,Sizeof(Lt),O); For I:=1 To N Do For J:=1 To N Do Read(F,GI,J.C); Close(F);End; Function Find: Integer; 寻找已经标号未检查的顶点Var I: Integer;Begin I:=1; While (I=N) And Not(LtI.L0)And(LtI.P=0) Do Inc(I); If IN Thru Find:= 0 Else Find:= I;End; Function Ford(Var A: Integer):Boolean;Var 用标号法找增广路径，并求修改量 I,J,M,X:Integer;Begin Ford:=True; Fillchar(Lt,Sizeof(Lt),0); LtS.L:=S; Repeat I:= Find; If i=0 Then Exit; For J:=1 To N Do If (LtJ.L= 0)And(GI,J.C0)or(GJ,I.C0) Then Beginif (GI,J.F0) Then LtJ.L:= I; End; LtI.P:=1; Until (LtT.L0); M:=T;A:=Maxint; Repeat J:=M;M:=Abs(LtJ.L); If LtJ.L0 Then X:= GM,J.C- GM,J.F; If XA Then A:= X; Until M= S; Ford:=False;End; Procedure Change(A: Integer);调整过程Var M, J: Integer;Begin M:= T; Repeat J:=M;M:=Abs(LtJ.L); If LtJ.L0 Then GM,J.F:=GM,j.F+A; Until M=S;End; Procedure Print; 打印最大流及其方案VAR I ,J: Integer; Max: integer;Begin Max:=0; For I:=1 To N DO Begin If GI,T.F0 Then Max:= Max + GI,T.F; For J:= 1 To N DoIf GI,J.F0 Then Writeln( I, - ,J, ,GI,J.F); End; Writln(TheMaxStream，Max)；End； Procedure Process；求最大流的主过程Var Del：Integer； Success:Boolean；Begin S:=1;T:=N; Repeat Success:=Ford(Del); If Success Then Print Else Change(Del); Until Success;End; Begin Main Program Init; Process;End. 源程序及数据文件 以上标号法求最大流的算法，只能适用于网络中的任意两点之间只有一条弧的情况，若任意两点之间有多条弧，则我们可以通过在这些弧中的每条弧上设置一个虚拟点，转化成任意两点间只有一条弧情况。三最小费用最大流 上面的网络，可看作为辅送一般货物的运输网络，此时，最大流问题仅表明运输网络运输货物的能力，但没有考虑运送货物的费用。在实际问题中，运送同样数量货物的运输方案可能有多个，因此从中找一个输出费用最小的的方案是一个很重要的问题，这就是最小代价流所要讨论的内容。 1)最小费用最大流问题的模型 给定网络N=(V，E，c，w，s，t)，每一弧(vi,vj)属于E上，除了已给容量cij外，还给了一个单位流量的费用w(vi,vj)O(简记为wij)。所谓最小费用最大流问题就是要求一个最大流f，使得流的总输送费用取最小值。 W(f)=wijfij 2)用对偶法解最小费用最大流问题 最小费用流问题的常用算法有两种：原始算法与对偶算法，下面只介绍对偶算法。 定义：已知网络N=(V，E，c，w，s，t)，f是N上的一个可行流，p为vs到vt(关于流f)的可增广路径，称W(p)=wij（p+）-wij（p-）为路径p的费用。 若p*是从vs到vt所有可增广路径中费用最小的路径，则称p*为最小费用可增广路径。 定理：若f是流量为v(f)的最小费用流，p是关于f的从vs到vt的一条最小费用可增广路径，则f经过p调整流量Q得到新的可行流f(记为f=f+Q)，一定是流量为v(f)+Q的可行流中的最小费用流。(证明参见有关运筹学资料)由于wij0，f=0就是流量为0的最小费用流(费用也为0)，所以初始最小费用流可以取f=0。 (1)对偶法的基本思路 取f=0 寻找从vs到vt的一条最小费用可增广路径p。 若不存在p，则f为N中的最小费用最大流，算法结束。 若存在p，则用求最大流的方法将f调整成f*，使v(f*)=v(f)+Q，并将f*赋值给f，转。 (2)迭代法求最小费用可增广路径 在前一节中，我们已经知道了最大流的求法。在最小费用最大流的求解中，每次要找一条最小费用的增广路径，这也是与最大流求法唯一不同之处。于是，对于求最小费用最大流问题余下的问题是怎样寻求关于f的最小费用增广路径p。为此，我们构造一个赋权有向图b(f)，它的顶点是原网络N中的顶点，而把N中每一条弧(vi，vj)变成两个相反方向的弧(vi，vj)和(vj，vi)。定义w(f)中的弧的权如下： 如果(fij0)，则bji=-wij ；如果(fij=cij)，则bji=+oo 于是在网络N中找关于f的最小费用增广路径就等价于在赋权有向图b(f)中，寻求从vs到vt的最短路径。求最短路有三种经典算法，它们分别是Dijkstra算法、Floyd算法和迭代算法。由于在本问题中，赋权有向图b(f)中存在负权，故我们只能用后两种方法求最短路，其中对于本问题最高效的算法是迭代算法。 为了程序的实现方便，我们只要对原网络做适当的调整。将原网络中的每条弧(vi，vj)变成两条相反的弧： 前向弧(vi,vj)，其容量cij和费用wij不变，流量为fij； 后向弧(vj,vi)，其容量0和费用-wij，流量为-fij。 事实上，对于原网络的数据结构中，这些单元已存在，在用标号法求最大流时是闲置的。这样我们就不必产生关于流f的有向图b(f)。同时对判断(vi,vj)的流量可否改时，可以统一为判断是否“fij0，则fji=-fij0=cji。 除此，为了求vs到vt的最短路径，设置一个数组best，其中结构如下。 type Tbest=record value，fa：integer； end； var best：array1.maxN) of Tbest；besti.value表示vs到vi的最短距离，besti.fa记录着vs到vi最短路径中vi的前趋顶点，以便于找到从vs到vt的增广路径。在每一次寻找最小费用可增广路径前，vs的value值设为0，其它顶点的value值设为MaxInt。 迭代法求最短增广路径的具体算法如下： Best赋初值(除源点的value值为0，其余点的value值均为MaxInt) repeat Quit:= True； for i:=1 to n do if 源点到i有道路 then for j:=1 to n do if (vi，vj)的流量可改进)and (i的value值+(vi，vj)j的value值)then begin j的value值 := i的value值+(vi,vj); j的fa值:=i; Quit:=false； end； until Quit； (3)流的调整 若找到vs到vt的最小费用可增广路径，则我们可以从bestt.fa开始反向跟踪找到整个从源点到汇点的可增广路径p，然后修改可增广路的流量，改进量Q=min|fij|；(vi，vj)p。注意，在修改增广路上的弧(vi,vj)的流量fij后，还要修改狐(vj,vi)的流量fji(fji=-fij)。 为了简化程序设计，下面的改进流的过程Add-Path，仅以1作为改进量。procedure Add_Path；var i,j:integer;begin i:=t; while is do begin j:=beati.fa；inc(Netj，i.f)； Neti，j.f:=-Netj，i.f;i:=j; end； inc(Minw，bestt.value)；end； 下面请大家编出求最小费用最大流的程序。程序要求的输入文件的格式如下：文件的第一行有两种整数N，表示网络中顶点数。第二行开始，每行描述网络中的一条弧的信息i，j，cij，wij，分别表示弧的起点与终点以及弧上的容量与单位流量通过该弧的费用。文件以连续的4个0表示输入结束。 四网络流算法的应用 网络流算法的效率为大约为O(E2V(f*)，其中E为网络中弧的数目，v(f*)为最大流的流值。因此网络流算法效率是多项式算法，仍然是个高效算法。在近年的竞赛中，网络流算法的应用越来越广，但竞赛中的问题大都看起来与流的问题似乎不相关。只要我们能构造出问题的网络流模型，就能应用流的算法高效的解决问题。 例1 最优工作问题(work) CCS集团有n台机器。为了生产需要，新招募了n名技术人员。他们有丰富的专业技术，每个人都熟悉各种机器的操作。现在每个人只能操作一台机器，而每个人对不同机器的控制能力又有差别，技术员i对机器j的控制能力称为ability(i，j)。要求给每人分配一台机器，使得所有人控制能力之和最大。 输入格式： 第一行仅有一个整数n(n=100)，第二行开始是一个n*n的矩阵，第i行第j列表示ability(i，j)(ability(i，j)=300)。 输出格式： 仅一行：包含一个整数S，表示最大控制能力和。样例：INPUTTXT3 5 23 2 87 5 8OUTPUTTXT20 问题分析 对于本问题，可以建立如图4-3所示的图，x1，x2，x3分别代表3个技术员，y1，y2，y3分别表示3台机器，有向边(xi，yj)表示xi控制机器yj，边上的权表示技术员对该机器的控制能力。显然图4-3是一个二分图。现在要求每个技术员唯一控制一台机器，且要控制能力之和最大。这样问题就转化为一个关于二分图求最佳匹配的问题。 图 4 - 3 图 4 - 4算法分析 下面用求最大流的算法，求最佳匹配。 (1)在二分图基础上，构造一个网络N(如图4-4)。 增加一