管理运筹学-07-网络规划1ppt课件

1、第一节：现实中的网络规划问题第一节：现实中的网络规划问题第二节：图的基本概念第二节：图的基本概念 第三节：树第三节：树 第四节：最大流问题第四节：最大流问题 第五节：最短路径问题第五节：最短路径问题 第六节：最小费用最大流问题第六节：最小费用最大流问题第七节：网络计划技术第七节：网络计划技术第八节：网络规划的应用第八节：网络规划的应用许多工程和管理的问题都可以用图与网络来描述，图与网络优化问题是一类应用十分广泛的问题。图与网络优化是线性规划等理论和算法在具有图结构的问题中的应用。由于图与网络问题具有特殊的结构，相应的优化算法也不同于一般的单纯形算法，具有其独特的直观和简捷的特点。哥尼斯堡城有条

2、河流，河中有两个小岛，河上共有七个桥，当地居民考虑这样一个问题：能否从某个地点任意点出发经过七个桥，且每个桥只经过一次，最后回到出发地点。 欧拉在1736年发表了图论方面的第一篇论文，解决了哥尼斯堡的七桥问题。欧拉将此问题归结为下图所示的一笔画问题。也就是能否从某一点开始，不重复地一笔画出这个图形，最后回到原来出发点。 BACD欧拉证明了这是不可能完成的。因为图形中的每个点都与奇数个线相关联，不可能将这样的图形不重复地一笔画出来，这是古典的图论中的一个著名问题。 7.2.1图: 由节点Node和边Edge组成。节点和边是图中最基本的概念，我们不对其作出定义。下图中，有4个节点，7条边，每一条边

3、都与2个节点对应。因此，一条边可以用它的两个节点来标记。图7.3中的边，可以记为v1，v2，v1，v3，v2，v3，v3，v2，v2，v4，v3，v4，v4，v1。 v3 v1 v4 v2 e1e2e3e4e5e6定义定义 设设V=V=v1v1，v2v2，vmvm表示节点的集合，表示节点的集合，E=E=e1e1，e2e2，enen表示边的集合，若对任一表示边的集合，若对任一ekEekE，均有，均有vivi，vjVvjV与之对应，则称与之对应，则称VEVE为图，记为为图，记为G=(VG=(V，E)E)。称称vivi为为G G的顶点，的顶点，ekek为为G G的边，记为的边，记为ek=viek=v

4、i，vj= vjvj= vj，vivi。称称vivi，vjvj为为ekek的端点，的端点，ekek为为vivi，vjvj的关联边。称的关联边。称vivi，vjvj为邻接为邻接点。点。将图将图7.37.3用数学定义表示如下：用数学定义表示如下：G=(VG=(V，E)E)V=V=v1v1，v2v2，v3v3，v4v4E=E=e1e1，e2e2，e3e3，e4e4，e5e5，e6e6，e1e1，e2e2，e3e3，e4e4，e5e5，e6e6，e7=v1e7=v1，v2v2，v1v1，v3v3，v2v2，v3v3，v3v3，v2v2，v2v2，v4v4，v3v3，v4v4，v4v4，v1 v1 如果

5、图中一个边的两个端点为同一个点，称这样的边为环。如果两个点之间存在两个以上的边，称为多重边。一个没有环、也没有多重边的图，称为简单图。无环,允许有多重边的图称为多重图。本章讨论的图主要是指简单图。图中的边是对节点的关系描述，所以我们讨论的图如果关系表示的相同，不论图的形状如何，我们认为这样的图都是相同的。次: 以点v为端点的边的个数称为v的次， 表示为: d(v)。悬挂点: 次为1的点。悬挂边: 悬挂点的关联边。孤立点: 次为0的点。奇点: 次为奇数的点。偶点: 次为偶数的点。定理定理7-1: 7-1: 图图G=(V,E)G=(V,E)中中, ,所有点的次之和是边数的两倍所有点的次之和是边数的

6、两倍, , 即即: :证明证明: :计算各端点的次时，每个边都用了两次，所以次数的计算各端点的次时，每个边都用了两次，所以次数的总和必然为边数的两倍。总和必然为边数的两倍。定理定理7-2: 7-2: 任意一图中任意一图中, , 奇点的个数为偶数。奇点的个数为偶数。证明证明: :设设 V1 V1表示奇点的集合，表示奇点的集合， V2 V2表示偶点的集合。由有：表示偶点的集合。由有： 因为偶点的次之和为偶数，总数为偶数，所以奇点的次之因为偶点的次之和为偶数，总数为偶数，所以奇点的次之和必须是偶数，只有偶数个奇数之和才能是偶数。所以奇和必须是偶数，只有偶数个奇数之和才能是偶数。所以奇点的个数必然为偶

7、数个。点的个数必然为偶数个。qvdVv2)(qvdvdvdVvVvVv2)()()(21链：点边交错系列，链：点边交错系列， 记为：记为： 如果满足如果满足 ，一般简记为：，一般简记为：圈：圈： 的链。的链。 初等链：点初等链：点 均不相同。均不相同。初等圈：点初等圈：点 均不相同。均不相同。简单链：链中边均不相同。简单链：链中边均不相同。简单圈：圈中边均不相同。简单圈：圈中边均不相同。连通图：任意两点之间至少有一条链。否则称为不连通图连通图：任意两点之间至少有一条链。否则称为不连通图连通分图：对不连通图，每一连通的部分称为一个连通分连通分图：对不连通图，每一连通的部分称为一个连通分图。图。支

8、撑子图：支撑子图： 对对G=G=（V V，E E），若），若G G=(V=(V,E,E), ), 使使V V=V, E=V, E E, E, 则则G G是是G G的一个支撑子图生成子图）的一个支撑子图生成子图）),.,(11211kkkiiiiiivevvevkiivv 1kiiivvv,.,21121,.,kiiivvv,1ttktiiivve),.,(121kkiiiivvvv前面讨论的图中，边是没有方向的，ek=vi，vj= vj，vi。这样的图称为无向图。但许多实际问题用无向图表示是不够的。例如，涉及交通网络中单行道、一项工程的各工序的前后次序关系等。 v3v1v4v2a1a2a3a4

9、a5a6a7定义定义 设设V=v1，v2，vm表示节点的集合，表示节点的集合，A=a1，a2，an表示边表示边的集合，若对任一的集合，若对任一akA，均有均有vi，vjV与之对应，则与之对应，则称称VA为图，记为为图，记为D=(V，A)。称称ak为为D的弧，记为的弧，记为ak=（vi，vj）（vj，vi）。）。 始点和终点始点和终点: : 对弧对弧a=(u,v), ua=(u,v), u为为a a的始点的始点, v, v为为a a的终点。的终点。基础图基础图: : 对对D=(V, A), D=(V, A), 去掉图上的箭头的无向图。去掉图上的箭头的无向图。链链: : 点弧交错序列点弧交错序列,

10、 , 若在其基础图中对应一条链若在其基础图中对应一条链, , 则称为则称为 D D的的一条链。一条链。路：假设路：假设 是是D D中的一条链，且中的一条链，且 ，t=1,2,k-1,t=1,2,k-1,称之为从称之为从 到到 的一条路。的一条路。回路回路: : 的路。的路。初等路初等路: : 路中点不相同。路中点不相同。初等回路初等回路: : 回路中点不相同。回路中点不相同。),.,(112211kkkiiiiiiivavavav),(1tttiiivva1ivkivkiivv 1如果给定一个图G=(V，E)或D=(V，A)的任一边弧有一个实数 与之相对应，由称这样的图为赋权无向有向图。赋权图

11、的应用是很广泛的。例如，在一个交通网络中，边的权数可以是两个点之间的距离，也可以表示两点之间的运输费用、运输时间、运输能力等。在一个设备维修的图中，权数可以表示维修费用，在工程项目计划网络图中可以表示各工序的完成时间等。ijw1354256-2023-44在赋权图中的链路上所有边弧对应的权之和，称为链路的权。一个连通图连同定义在其边集上的实函数一起，称为一个网络图形虽然有直观等优点，但随着实际问题的大型化，大多数算法需要在计算机上运算和求解，计算机处理直观图形是比较困难的。以下介绍将图用矩阵表示，将图的几何形状转化为代数矩阵，可以方便计算机对图形的处理与运算。以下举例说明。例7-1将下7-5用

12、矩阵表示。V1V2V3V4V5V6V7V10111000V21011100V31100110V41100101V50111011V60010101V70001110两个端点之间有边记为1，无边相连则记为0，对角线上记为0。这样得到一个对称的矩阵。 V1V2V3V4V5V6V7V10347V230324V343057V472026V5452014V670102V76420两个端点之间有边相连的，记上其权数，无边相连的记为，对称线上仍记为0。赋权无向图的矩阵也是对称矩阵。 例例7-27-2将下将下7-67-6用矩阵表示。用矩阵表示。312453564357赋权有向图的矩阵往往不是对称矩阵V1V2V

13、3V4V5V1053V2054V3607V40V530树是一类特殊的图。例如连接五个乡镇的光纤网，可表示下图31245树树Tree）：无圈的连通图称为树）：无圈的连通图称为树图的支撑树图的支撑树Spanning TreeSpanning Tree）: :设图设图G G有有p p个节点，个节点，q q条边条边。由。由G G中中p p个节点，个节点，p-1p-1条边组成的树称为图条边组成的树称为图G G的支撑树，也的支撑树，也称为图称为图G G的生成树。的生成树。图7-8 图7-5的一个支撑树图7-9 图7-5的一个支撑树树中只与一条边关联的节点称为悬挂点。与悬挂节点关联的边称为悬挂边。图7-8中

14、节点3和节点7都是悬挂点，6，3和4，7都是悬挂边。树有以下性质：（1任何树至少有两个悬挂点。图7-8中节点3，节点7。（2如果树的节点数是p，则边的个数为p-1。图7-8的图有5个节点，有4条边。（3树中任意两个节点之间只有唯一的一条链。（4在树中任意两个不相邻的节点之间增加一条边，则会形成圈。 一个连通图可以有多个支撑树。支撑树的权:若T=(V,E) 是G的一个支撑树, E中的所有边的权之和称为支撑树的权, 记为w(T):例如图7-8的总的权为28，图7-9的总的权为13。最小支撑树：图的权最小的支撑树，即：比如，在一个小区铺设光缆通讯网，只要各个楼都连通即可，希望用的光纤越少越好。Tvv

15、ijjiwTw,)()()(min*TwTwT解法一：破圈法解法一：破圈法解法二：避圈法解法二：避圈法 解法三：顶点扩充法解法三：顶点扩充法例例7-37-3设某个小区由六个楼组成，如图设某个小区由六个楼组成，如图7-107-10，图上的数字，图上的数字为各相邻楼的距离百米）。现要铺设光纤，试求光纤总长为各相邻楼的距离百米）。现要铺设光纤，试求光纤总长度最短的铺设方案。度最短的铺设方案。153232213v4v2v1v5v64v3用破圈法求解过程如下：一般先找权数最大的边所在的圈 （1找圈找圈v1，v2 ，v4，v1或或v1，v3 ，v4，v1去掉边去掉边v4，v1，13232213v4v2v1

16、v5v64v3图7-11. 破圈法求解示意图1） （2去掉边去掉边v4，v5（3去掉边去掉边v3，v6（4去掉边去掉边v3，v1（5去掉边去掉边v2，v5。得图得图7-12。此时图中已不含圈，。此时图中已不含圈，剩下的边构成了原网络的最小剩下的边构成了原网络的最小支撑树，也就是铺设光纤的最支撑树，也就是铺设光纤的最优方案。优方案。最小树的权为：最小树的权为：W(T*)=1+2+2+2+1=812221v2v1v5v6v4v3图7-12. 破圈法求解示意图2）避圈法与破圈法的思想相反，先将所有边的权按从小到大的次序排列，然后依次检查，如果某个边加到图上不会产生圈，就将其加上，否则就不加到图上。直

17、到所有边都检查完为止。在图7-9中加边的顺序为v1，v2、v4，v6、v2，v4、v3，v4、v5，v6，由于本图为6个点，加上5个边即完成。得到如图7-11的结果，与破圈法得到的结果相同。一般来说，一个图可以有多个不同的最小支撑树，但它们的总权一定相同。 顶点扩充法是先在图中任选一个点，记为S=a1，以该点为出发点，将与其相连的最小权的边加入图中，将相关连的点加入到S中，得到S=a1，a2；再寻找与S中的点相连的边中权数最小的边加入图中，将相关连的点加入到S中，反复进行以上步骤，直到所有的点都加入到S中为止。即可得到最小支撑树。 以v4做为出发点，S=v4，与v4相连的边有5条，权数最小的为

18、v4，v6，将v6加入S中，S=v4，v6；与S=v4，v6相连的边有7条，其中权数最小的有3条，权数都是2，此时可任选一条。如将v5加入，得S=v4，v6，v5；与S=v4，v6，v5相连的边有5条，其中权数最小的有2条，权数都是2，此时可任选一条。如将v2加入，得S=v4，v6，v5，v2；与S=v4，v6，v5，v2相连的边有4条，其中权数最小的有1条，权数是1，将v1加入，得S=v4，v6，v5，v2，v1；与S=v4，v6，v5，v2，v1相连的边有3条，其中权数最小的有1条，权数是2，将v3加入，得S=v4，v6，v5，v2，v1，v3。此时所有点都加入到S中，可以得到如图7-12

19、的结果。 153232213v4v2v1v5v64v3在网络图中指定一个源节点和一个汇节点，源节点的供应量为f，汇节点的需求量为f，图中其他节点均为中转节点。图中各边i，j流量的下界Lij=0，上界cij 0图7-13）。对于一个给定的图，各节点流入、流出的流量保持平衡，各边上的流量为非负且不超过相应边的流量上界，求通过图的最大流量f的问题就是网络最大流问题。23411342f2cij图7-13. 最大流示意图（一网络与流（一网络与流定义定义: :有向图有向图D=(V,A)D=(V,A)，其中，其中vs vs 表示始点，表示始点，vt vt 表示表示终点，其余点为中间点，对每个弧对应一个权终点

20、，其余点为中间点，对每个弧对应一个权c(vi,vj)c(vi,vj)，称为弧，称为弧(vi,vj)(vi,vj)的容量，简写为的容量，简写为cij cij 。称这样。称这样的赋权有向图为一个网络，记为的赋权有向图为一个网络，记为D=(V,A,C) D=(V,A,C) 。 一个网络图要求只有一个始点、一个终点。一个网络图要求只有一个始点、一个终点。 对于网络D=(V,A,C)中的每个弧(vi,vj)定义一个实数fij ，称为弧(vi，vj)上的流量。则集合 F=fij(vi,vj)A称为此网络的一个流满足以下条件的F=fij(vi,vj)A称为一个可行流：称为可行流的流量有对有对有对平衡条件（对

21、容量限制条件ffffvfffvfftsivcfAvvAvvjtAvvtjtAvvjsAvvsjsAvvjiAvvijiijijjitjjtsjjsijji),(),(),(),(),(),( : :0:,:)20 ),:) 1也就是说，一个可行流的每个弧上的流量不超过该弧的容量、中间点流入量与流出量相等、始点的净流出量与终点的净流入量相同。可行流总是存在的，例如所有的fij=0的流F=fij=0(vi,vj)A即是一个可行流，称为零流。在一个网络中，使f达到最大的可行流称为最大流。网络最大流问题可以用线性规划方法求解。例如图7-13的最大流问题，设xij为各弧的流量，f表示可行流的流量。则此最

22、大流问题的线性规划形式为： 23411342f2c ijijijcxfxxxxxxxxfxxt sfz040302010. .max34243423132423121312节点节点节点节点在网络D=(V,A,C)中，将点集V分成不相交的两个非空集合V1与 ，始点vs在V1中，终点vt在 中，则把起点在V1中且终点在中的弧构成的集合称为分离vs 和vt的截集，记为V1， ）将截集中所有弧的容量之和，称为截集的容量，简称为截量。记为：),(),(1111),(VVjiijcVVC1V1V1V1V23411342f2cij23411342f2cij23411342f2cij23411342f2cij

23、图7-14图7-15图7-16图7-171V1V1V（V1，C(V1，V1（V1，）C(V1， ) 图7-141，23，4（1，3）（2，3）（2，4）c13+c23+c24=4+2+3=9图7-1512，3，4（1，2）（1，3）c12+c13=1+4=5图7-161，32，4（1，2）（3，4）c12+c34=1+2=3图7-171，2，34（2，4）（3，4）c24+c34=3+2=51V1V1V截集是一种特殊的集合，如图7.16中2，3不包含在截集中。如果将任意一个截集中的所有弧去掉，将不存在从网络始点到终点的路了，但可能存在从网络始点到终点的链。将截集容量最小的截集称为最小截集。如（

24、1，2）（3，4），其截量为3。 定理定理7-37-3： 网络任一可行流的流量网络任一可行流的流量f f必定小于或等于网络中必定小于或等于网络中任一截集的容量。即：任一截集的容量。即：定理定理7-47-4： 网络中从网络中从vs vs 到到vt vt 的最大流的流量等于分离的最大流的流量等于分离vs vs 和和vtvt的最小截集的截量。的最小截集的截量。即即: :假设假设 是一个最小截集，是一个最小截集，F F* *是最大流，最大流量为是最大流，最大流量为f f* *，则有图，则有图7-17.7-17.截集示意图截集示意图),(min111kkSkVVCf),(*1*1VV),(*1*1*VV

25、CffsiejmkV1f图7-18.截集示意图1V设是网络D中的一条从vs到vt的链，定义链的方向为从vs指向vt，则链上与链的方向一致的弧称为前向弧，其集合记为；链上与链的方向相反的弧称为后向弧，其集合记为- 。 1534762(4,4)(10,7)(4,4)(8,1)(1,1)(8,4)(6,3)(7,7)(2, 2)(3,3)(3,3)(10,5)如图中，弧上的数字表示为cij，fij），该流是一个可行流。其中的一条链=v1，v4，v5，v6，v7各弧分为如下两类： = ( v1，v4)，( v4，v5)，( v6，v7)- = ( v6，v5)对于一个可行流对于一个可行流F F， 是从

26、是从vs vs 到到vt vt 的一条链，如果的一条链，如果 上的各上的各条弧的流量满足以下条件：条弧的流量满足以下条件： fij cij fij 0 fij 0 当当( vi( vi，vj)vj)- - （后向弧不为零）（后向弧不为零）则称则称 为关于可行流为关于可行流F F的一个增广链。的一个增广链。如果一个可行流存在增广链，就可以将可行流进行调整。令 1 =min cij -fij | ( vi，vj) 2 =min fij | ( vi，vj)- = min1，2 再令 fij+ ( vi，vj)fij = fij- ( vi，vj)- fij ( vi，vj) 则可得到一个新的可行流

27、F，使得 f=f+由于0，所以新的可行流的流量一定可以得到增加。因此，当一个可行流F存在增广链时，F就不是最大流。这个思想同时也给出了一种沿增广链调整流量，从而得到最大流的方法 定理定理7-4：设：设F=fij(vi,vj)A是是D=（V，A，C的一的一个可行流，则个可行流，则F*为最为最大流的充要条件是网大流的充要条件是网络中不存在关于络中不存在关于F的的增广链。增广链。 此方法是福特和富尔克逊于1956年提出的，所以称为福特富尔克逊标号法。（一基本思想 从某一可行流 F如零流出发，按一定规则找出一条增广链，并按照前述的沿增广链进行流量调整的方法去调整F，得到一个流量增大 的新可行流 F。重

28、复上述做法直到找不出增广链为止，这时就得到一个最大流，同时还可以得到一个最小截集。 （二基本步骤1. 给始点 vs 标号0，），那么 vs 已标号待检查； 2. 取一个已标号待检查的点 vi对所有与 vi 相邻而未标号的点 vj 依次判断、执行如下手续： （1若关联 vj 与 vi 的弧为(vi, vj)，则当该弧上的流量 fij 0 时, 给 vj 标号( -vi，b(vj)，其中 b(vj) = min b(vi)，fji 表示 (vi, vj) 弧上的流量的最大可减少量；而当 fji = 0 时, 不给 vj 标号； 当所有与 vi 相邻而未标号的点 vj 都执行完上述手续后，就说明点

29、vi 已检查完毕。vj为已标号未检查的点。3. 反复 2的手续，可能出现两种结果：（1终点 vt 得到标号。则从vt回溯标号点第一个标号，就能找出一条由标号点和相应的弧连接而成的从 vs 到 vt 的一条增广链 (F)，转 4；（2所有标号点均已检查过，而vt又未得到标号。这说明不存在增广链，而当前的可行流即为最大流，计算出其流量，算法终止。4. 取调整量 = b(vt) （即终点 vt 的第二个标号）,令 fij = fij + ， 对一切 (vi, vj) fij = fij - ， 对一切 (vi, vj) - 非增广链上的各弧流量 fij 不变。5. 删除网络中原有一切标号，前往 1。

30、注：标号中的第一个标号表示给该点标号的点，第二个标号表示调整量。534762(4,4)(10,7)(4,4)(8,1)(1,1)(8,4)(6,3)(7,7)(2, 2)(3,3)(3,3)(10,5)(0,)1(v1,7)(-v4,3)(v4,4)(v6,2)图7-20. 可行流1）(v1,3)(-v5,2) 图7-21. 可行流2）534762(4,4)(10,7)(4,4)(8,3)(1,1)(8,6)(6,3)(7,7)(2, 0)(3,3)(3,3)(10,7)(0,)1(v1,5)(v1,3)(-v4,3)(v4,2)上例中说明了标号法的基本思想，在解最大流问题时一般可以从零流出发

31、，在图上直接给出标号，找到从vs到vt的一个增广链和相应的调整量，并进行流量的调整，重复以上步骤直到找不到增广链为止。即可得到最大流和最小截集。最大流不一定是唯一的，但最大流的流量一定是唯一的；最小截集也不一定是唯一的，最小截量一定是唯一的，而且与最大流的流量是相同的。最短路问题就是在一个网络图中，给定一个起点vs和一个终点vt，寻找vs到vt的路，使该路为从vs到vt的所有路中权数最小的路。实际问题中最短路问题有广泛的应用。例如管道铺设、线路安排、运输线路选择、工厂布局、设备更新等问题。解法：标号法矩阵法 最短路的标号法是由狄克斯屈E.W.Dijkstra于1959年提出的，是目前公认的求解

32、权数为非负的网络最短路问题较好的算法。这种算法能够求出网络中任意一点出发到其它各点的最短路。算法的思想如下：对每一个网络中的点vj，均赋予一个标号，永久标号Pvj或临时标号Tvj）。其含义如下：Pvj）从起点vs到vj最短路的长；Tvj）从起点vs到vj最短路的长的上界。一个点只能有上述两种标号之一，如果有了P标号就不再改变了，如果有T标号则根据情况进行修改。该算法的基本思想就是先给vs点标号为Pvs）=0，其余点标号为Tvj）=；然后检查有P标号的点，对与该点有关联边的vj的T标号进行修改；在所有T标号中找一个最小的，将其T标号修改成P标号。再检查新得到P标号的点，修改其它点的T标号，再在所

33、有T标号中找最小的修改为P标号；如此反复，直到要求的终点或所有点得到P标号为止，即可得到网络最短路。因为此算法一次修改一个P标号，所以如果网络中有N个点，最多经过N-1步就能找出要求的最短路。为了寻找到vs各点的最短路线，给每个顶点一个 值，算法终止时，假设 表示在从vs到vj的最短路上vj的前一个点为vm；假设 ，则表示vs到vj不存在路则表示vj为起点。 ,)(mvjMvj)(（1给vs标上永久标号P(vs)=0，其余节点标上临时标号T(vj)=，同时给各点vj赋值如下：（2若节点vi是刚得到P标号的点。把与vi有弧边直接相连而且有T标号的节点，对其T标号和 进行如下修改： 若T(vj)P

34、vi）+wij，则T(vj)=Pvi）+wij ；（3把T标号中值最小的节点vj0的临时标号T(vj0)改为P(vj0)，如果所有点均有P标号、或要求的终点有P标号、或无法继续修改时，则算法终止；否则转2）。 0)( )( )(ssjjsjjvvvMvvvvTivj)(步骤V1V2V3V4V5V6V7V800 0MM MMMMM151316 1MMMM2514 3M103MM3518464MM48464MM576126M695M7M15347627356422121681用表格的一行表示一个步骤，表格中的左上角表示PT标号，其中表示P标号；右下角表示 值到各点的最短路的长就是各点的P标号之值。

35、到各点的最短路线可从该点的最后的值出发，逆序寻找其前一点的值，直到起点为止，即可得到从起点到该点的最短路线。例如：P(v7)=9，说明从v1到v7的最短路长为9 （v7）=5 （v5）=6 （v6）=4 （v4）=3 （v3）=1 v7 v5 v6 v4 v3 v1点最短路最短路的权V1起点0V2v1 v25V3v1 v33V4v1 v3 v4 4V5v1 v3 v4 v6 v57V6v1 v3 v4 v6 6V7v1 v3 v4 v6 v5 v79V8无对于无负权的无向图来说，标号法的程序也是相同的。 当一个网络存在负权时，Dijkstra算法会失效。如图7-23 13232-3 图7-23

36、. 负权网络从v到v3的最短路长为-1，而不是2。(1)(,)sjsjdvvw),(min),()1()2(ijisjswvvdvvd),(min),() 1()(ijiskjskwvvdvvd矩阵法的基本思想是利用本章第一节中介绍的网络图的矩阵表示，其中的wsj表示从vs经一步到vj的权，可记为：则从vs经K步到达vj的权为：普通，经K步从vs经两步到达vj的权为Sj1in),()1(iskvvdk-1步 1步 ijwnjnskjskjskjskwvvdwvvdwvvdvvd),(),(),(min),()1(22)1(11)1()(),(min)1(ijiskwvvd),(),()1()(

37、jskjskvvdvvdjsvv 到),(),()1()(jskjskvvdvvdjsvv 到由于 的计算就是n 个对应元素的求和取小，这与矩阵的乘法的计算是相类似的，所以此算法也称矩阵摹乘法。当（j=1,2,n时，说明从的最短路的权不能再减少，所以（j=1,2,n即为的最短路的权。 第8章 网络分析52 0 3 2 4 0 3 2 4 0 4 4 1 0 4 4 1 0 -1 6 0 -1 6 3 -2 0 1 3 -2 0 1 5 0 3 5 0 3 3 3 0 3 3 0 W =例例从至从至 1 1 2 2 3 3 4 4 5 5 6 6 1 1 2 2 3 3 4 4 5 5 6 6

38、1 1 3 3 4 4 6 6 2 2 5 5 34253-2-24413613-1-13第8章 网络分析53二、求各点至某点的最短路二、求各点至某点的最短路 1 1 n n r r j j 1步步k-1步步dk=d(k)1r.d(k)ir.d(k)nr 1 1 2 2 3 3 负回路负回路d(k) = min wij + d(k-1) 1j n irjr dk=w* dk-1 ， k=2，3, ,n -1dk= dk-1 则也结则也结束束若不含负回路，若不含负回路，至多算到至多算到 dn-1。wijd(k-1)jr第8章 网络分析54* 4 4 1 1 3 3 0 0W * d1 =0 3

39、2 0 3 2 4 4 0 4 4 1 0 4 4 1 0 -1 6 0 -1 6 3 -2 0 1 3 -2 0 1 5 5 0 30 3 3 3 0 3 3 04 4 1 1 -2 -2 -1 -1 3 3 0 0 0 0 1 1 -2 -2 -1 -1 3 3 0 0 0 0 1 1 -2 -2 -1 -1 3 3 0 0从从 至至 1 1 2 2 3 3 4 4 5 5 6 6 1 1 2 2 3 3 4 4 5 5 6 6d2d1d3d4d54 41 19 9-1-13 30 0d(2) = min w1j + d(1) j616= min 0+4, 3+1, 2+, +, +3,

40、4+0 0 3 2 4 = 4d(k) = min wij + d(k-1) 1j n irjr 0 4 4 1 0 -1 6 3 -2 0 1 5 0 3 3 3 0第8章 网络分析55* 4 4 1 1 3 3 0 0W * d1 =0 3 2 0 3 2 4 4 0 4 4 1 0 4 4 1 0 -1 6 0 -1 6 3 -2 0 1 3 -2 0 1 5 5 0 30 3 3 3 0 3 3 04 4 1 1 -2 -2 -1 -1 3 3 0 0 0 0 1 1 -2 -2 -1 -1 3 3 0 0 0 0 1 1 -2 -2 -1 -1 3 3 0 0从从 至至 1 1 2

41、2 3 3 4 4 5 5 6 6 1 1 2 2 3 3 4 4 5 5 6 6d2d1d3d4d54 41 19 9-1-13 30 021-1-1-2-203 4 4 2 2 6 6 2 2 6 6 6 6最最 短短 路路 1 1 2 2 3 3 4 4 5 5 6 6 3 3 6 6 4 4 2 2 6 6 6 6 按按W W阵中画圈元素的从阵中画圈元素的从 至关系至关系0 0 1 1 -2 -2 -1 -1 3 3 0 0最短路长最短路长 1 1 3 3 4 4 6 6 2 2 5 5 34253-2-24413613-1-132 -1-1 -2-2 +1 = 0第8章 网络分析56

42、 3 3 1 1 3 3 4 4 1 1 1 10 0 -1 -1 2 2 1 1 2 2 0 0最最 短短 路路最短路长最短路长 1 1 2 2 3 3 4 4 5 5 6 6 1 1 4 4 1 1 3 3 4 4 2 2 l2T=l1T * W = 1 1 2 2 3 3 4 4 5 5 6 6至至 从从 1 1 2 2 3 3 4 4 5 5 6 6 0 3 2 0 3 2 4 4 0 4 4 0 4 4 1 1 0 -1 6 3 -2 0 1 5 5 0 30 3 3 3 0 3 3 0( 0 3 2 ( 0 3 2 4 )4 )* *( 0 3 2 1 7 ( 0 3 2 1 7

43、4 )4 )( 0 -1 2 1 2 ( 0 -1 2 1 2 4 )4 )( 0 -1 2 1 2 ( 0 -1 2 1 2 0 )0 )( 0 -1 2 1 2 ( 0 -1 2 1 2 0 )0 )l3T=l4T=l5T= 3 3 1 1-1-11 11 1三、三、 求某点至各点的最短路求某点至各点的最短路2 2设一个图G中wij为节点i到节点j的距离，求节点1到节点m的最短路径。这就是图最短路径问题。设节点1为供应节点，供应量b1=1，节点m为需求节点，需求量bm=-1，其他节点i均为转运节点，bi=0。1 , 0, 11101. .min),(),(),(ijGikkiGjiijGj

44、iijijxmimiixxtsxwz第三节讨论了网络最大流问题，在实际中涉及流的问题时，人们考虑的不只是流量，同时要考虑“费用的因素。对D=(V,A,C), 给定一个单位流量的费用bij0, 最小费用最大流即:求一最大流f, 使Avvijijjifbfbfb),()(min*)(最大流的算法是从某个可行流出发，寻找关于可行流的增广链，然后沿着增广链调整可行流的流量，得到一个新的可行流，反复以上过程即可得到最大流。对于增广链, 若调整流量=1, 那么新可行流F的费用比原可行流F的费用增加量为:称为增广链的费用。ijijbbFbFb)()(可以证明，若F是流量为f的所有可行流中费用最小的，而是关于

45、F的费用最小的增广链，那么沿着增广链去调整流量，得到的新可行流F，就是流量为f的费用最小的可行流。这样当F为最大流时，也就是所求的最小费用最大流。由于bij0，所以零流的费用总是最小的。所以可以从零流出发去寻找最小费用最大流。这里主要需要解决的问题就是如何寻找关于F的费用最小的增广链。为此，可构造网络图D的相对应的赋权有向图WF），其节点与原网络图D相同，将D中的每一条弧，都变成两方向相反的弧，与，定义WF中弧的权为：权数为的弧表示不能通过，可以在WF中省略。这样寻找关于F的费用最小增广链的问题就等价于在WF中寻找从网络始点到终点的最短路问题。0 0 ijijijjiijijijijijijffbwcfcfbw权数为的弧表示不能通过，可以在WF中省略。这样寻找关于F的费用最小增广链的问题就等价于在WF中寻找从网络始点到终点的最短路问题。具体算法为：从零流出发，构造其WF），在WF中寻找最短路，在F中对应一个增广链，增广链的调整量由