1、运运 筹筹 学学6.7 习习 题题本章内容重点本章内容重点 6.1 图与网络图与网络6.2 树树6.3 最短路问题最短路问题6.4 网络最大流问题网络最大流问题6.5 最小费用最大流最小费用最大流6.6 案例：网络的中心与选址问题案例：网络的中心与选址问题第六章第六章 网络规划与网络分析网络规划与网络分析概概 述述n图论是目前运用十分广泛的运筹学分支之图论是目前运用十分广泛的运筹学分支之一一；n自自1736年著名数学家欧拉年著名数学家欧拉(Euler)解决了有解决了有名的哥尼斯堡七桥问题以来，图论取得了名的哥尼斯堡七桥问题以来，图论取得了十分迅速的发展十分迅速的发展；n 已广泛应用于计算机、信
2、息论、经济科已广泛应用于计算机、信息论、经济科学等各领域，用以解决各种各样的决策问学等各领域，用以解决各种各样的决策问题。题。概概 述述n生活中的许多问题都可以运用图论的理论生活中的许多问题都可以运用图论的理论与方法来解决。例如：与方法来解决。例如：l在生产的组织与管理中，为了完成某项生在生产的组织与管理中，为了完成某项生产任务，各工序之间如何衔接，才能使任产任务，各工序之间如何衔接，才能使任务完成得既快又好？务完成得既快又好？l在城市水、电、煤气供应问题中，管道与在城市水、电、煤气供应问题中，管道与供电线路如何铺设，才能做到既满足要求，供电线路如何铺设，才能做到既满足要求，又使总费用最省？又
3、使总费用最省？6.1 6.1 图与网络图与网络n自然界和人类社会中许多事物以及事物之自然界和人类社会中许多事物以及事物之间的关系，都可以用点和线连接起来的图间的关系，都可以用点和线连接起来的图形来描述。形来描述。n例如用点表示城市，点间联线表示城市间例如用点表示城市，点间联线表示城市间的道路，就可描述城市间的交通，的道路，就可描述城市间的交通，哥尔斯保七桥问题：哥尔斯保七桥问题：哥尔斯保城有哥尔斯保城有一条普雷尔河，该河上有两个小岛，一条普雷尔河，该河上有两个小岛，河上有七座桥将这两个小岛及岛与河上有七座桥将这两个小岛及岛与河岸之间连接起来。河岸之间连接起来。CDAB 问题问题是要从是要从A,
4、B,C,DA,B,C,D这四块陆这四块陆地中的任何一块开地中的任何一块开始，通过所有的桥始，通过所有的桥一次且仅一次，最一次且仅一次，最后回到开始出发的后回到开始出发的这块陆地。这块陆地。n如果联线旁标注城市间的距离如果联线旁标注城市间的距离网络图网络图中称为中称为权权，形成加权图，就称为，形成加权图，就称为网络图网络图，就可进一步研究从一个城市到另一个城市就可进一步研究从一个城市到另一个城市的的最短路径最短路径；或者标上单位运价，就可分；或者标上单位运价，就可分析析运费最小运费最小的运输方案。的运输方案。例例6-1图图a表示表示5个球队之间的赛事关系。个球队之间的赛事关系。其中点其中点 a,
5、b,c,d,e,f 分别表示分别表示5个球队，个球队，两点的连接表示两球队之间的赛事关两点的连接表示两球队之间的赛事关系。系。从图中可反映出从图中可反映出a球队球队分别与分别与b，c，d 球队有球队有赛事；球队还与赛事；球队还与c球队，球队，d球队还与球队还与e球队有赛球队有赛事事。图图a 这这5个球队之间的关系也可用图个球队之间的关系也可用图b)来反映。来反映。图图a)与与b)没有本质的差异没有本质的差异 可见表示球队间有无赛事关系是两点间可见表示球队间有无赛事关系是两点间的连线，而图中点的相对位置如何、点与的连线，而图中点的相对位置如何、点与点之间联线的长短曲直，对反映对象之间点之间联线的
6、长短曲直，对反映对象之间的关系并不重要。的关系并不重要。图图b例例 6-2 图图 6-2 是一张管道运输网示意图，是一张管道运输网示意图，代 表代 表 7 个 城 市 间 物 资 运 输 关 系，个 城 市 间 物 资 运 输 关 系，v1,v2,v3,v4,v5,v6,v7表示表示7个城市，箭线旁个城市，箭线旁数字表示物流的最大容量。现在要求出数字表示物流的最大容量。现在要求出从从v1地到地到v7地的运送的最大流方案。地的运送的最大流方案。图图 6-2 是由点及带箭头的连线所组成的图形。是由点及带箭头的连线所组成的图形。为区别起见，为区别起见，把两点间不带把两点间不带箭头的连线称箭头的连线称
7、为为，带箭头，带箭头的连线称为的连线称为。n用图来描述事物间的联系，不仅直观清晰，用图来描述事物间的联系，不仅直观清晰，且网络图的画法简便，不必拘泥于比例和且网络图的画法简便，不必拘泥于比例和曲直。曲直。n这里所讲的图是反映对象之间关系的一这里所讲的图是反映对象之间关系的一种工具。电路网络、城市规划、信息传种工具。电路网络、城市规划、信息传递、物质结构、物资调配等也都可以用递、物质结构、物资调配等也都可以用点和线连接起来的图进行模拟。点和线连接起来的图进行模拟。定义定义6-1 无向图是一个有序二元组（无向图是一个有序二元组（V，E），记为），记为G=（V,E），其中），其中V=(v1，v2，v
8、p)是是p个点的集合，简称个点的集合，简称定点集定点集；E=（e1，e2，eq）是条边的集合，简称）是条边的集合，简称边集合边集合，并且是一个无序二元组。记为，并且是一个无序二元组。记为（1）无向图）无向图,iijjiijevvvvvvV由点和边由点和边组成的图称为组成的图称为无向图无向图，如图，如图 6-1。图图 6-3即为无向图，图中：即为无向图，图中：12345(,)Vvvvvv128(,.,)Eeee顶点数：顶点数：点集点集V中中元素的个数称为图元素的个数称为图G的顶点数，的顶点数，记为记为 。()|p GV如图如图 6-3，()5p G()|q GE如图如图 6-3，()8q G端点
9、端点：对于边：对于边,iijevvE，e为为vi,vj的关联边。的关联边。图图 6-3 中，中，12,vv 为为2e 的端点，的端点，2e 为为12,vv 的关联边。的关联边。称称vi，vj为为e的端点。的端点。若点若点 vi,vj有边相连，即有边相连，即,ijevvE则称则称vi,vj 相邻，相邻，vi,vj 与与e关联关联。如图如图6.3 中，中，v3,v5相邻，相邻，v3,v5与与e7关联关联。图图6.3（2）简单图）简单图环（自回路）环（自回路）：一条边的两个端点如果相同，：一条边的两个端点如果相同，称此边为环。如图称此边为环。如图6-3中的中的e1。多重边多重边：两个点之间多于一条边
10、的，如图：两个点之间多于一条边的，如图6-3中的中的e4，e5.不含环和多重边的图称不含环和多重边的图称为为简单图简单图，含有多重边的图称为多含有多重边的图称为多重图重图。(3)点的次（度）点的次（度）以点以点v为为端点的边数叫做点端点的边数叫做点v的次，记作的次，记作d(v)。如图如图6-3中，中，d(v1)=4，d(v2)=4。若若12(,.,)pVvvv，则称，则称12(),(),.,()pd vd vd v称为图称为图G的次序列。的次序列。次为次为 1 的点称为的点称为悬挂点悬挂点，连接悬挂点的边称为连接悬挂点的边称为悬挂边悬挂边。次为次为 0的点称为的点称为孤立点孤立点。次为奇数的点
11、称为次为奇数的点称为奇点奇点，次为偶数的点称为次为偶数的点称为偶点偶点。定理定理 6-1 任何图任何图G=（V,E）中，所有点的次）中，所有点的次数之和等于边数的数之和等于边数的2倍。倍。即即n证：由于每条边必有两个顶点关联，在计证：由于每条边必有两个顶点关联，在计算点的次时，每条边均被计算了两次，所算点的次时，每条边均被计算了两次，所以顶点次数之和等于边数的以顶点次数之和等于边数的2倍。倍。()1()2()pGiidvqG定理定理 6-2 任何图任何图G=（V,E）中，奇点的个中，奇点的个数必为偶数。数必为偶数。n证：设图证：设图G中奇点与偶点的集合分别为中奇点与偶点的集合分别为V1和和V2
12、，由定理由定理 6-1 知知12()()()2()iViViVdvdvdvqG12VVV由于由于2q(G)为偶数，而为偶数，而 是若干个偶数是若干个偶数之和，也为偶数。所以之和，也为偶数。所以 必为偶数，必为偶数，即奇点的个数即奇点的个数 必为偶数。必为偶数。2()iVd v1()iVd v1|V（4）链）链链链：对于无向图：对于无向图G=（V,E）,称顶点和边交替的序列称顶点和边交替的序列 为连接为连接 的一条链，的一条链，简记为简记为 其中其中 ,称称 为链的为链的两个端点。图两个端点。图6-3 中的中的都是链。都是链。两个端点重合的链，称为两个端点重合的链，称为圈圈。在一个图中，如果。在
13、一个图中，如果任何两个顶点之间都有一条链，该图称为连通图。任何两个顶点之间都有一条链，该图称为连通图。1iitvv和1122,(1)(1),iiiiitititvevevev12,iiitvvv(1)(,),1,2,1ikikikveekt 1232451245,vvvvvvvvvv1iitvv和有向图是一个有序二元组（有向图是一个有序二元组（V,A），记为），记为D（V,A），），其中其中 是是p个顶点的集合，个顶点的集合，是是q条弧的集合，并且条弧的集合，并且 是一个有序二元组，记为是一个有序二元组，记为 并称并称 是以是以vi为始点，为始点，vj为终点为终点的弧，的弧，i，j的顺序不能颠
14、倒，图中弧的方向用箭头标的顺序不能颠倒，图中弧的方向用箭头标识。由点和弧组成的图称为有向图，如图识。由点和弧组成的图称为有向图，如图6-4。图中：。图中：12(,.,)pVvvv12(,.,)qAaaaia(,)(,),ijijjiijav vvvv vV12345,Vvvvvv129(,.,)Aaaaija两个端点重合的弧称环。如图两个端点重合的弧称环。如图 6-4 中的中的a1.图图6-4n两个端点之间的同向弧数大于等于两个端点之间的同向弧数大于等于2，称，称为为多重弧多重弧。n无环也无多重弧的有向图称为无环也无多重弧的有向图称为简单有向简单有向图。图。以点以点v为起点的弧数叫做点为起点的
15、弧数叫做点v的出次，记作的出次，记作以点以点v为终点的弧数叫做点为终点的弧数叫做点v的入次，记作的入次，记作称称 为点为点v的次。的次。()dv()dv()()()dvdvd v在有向图在有向图D=(V,A)中，点和弧交替的序列中，点和弧交替的序列1122,(1)(1),iiiii ti titPvavavav，若有，若有(1),ititi tavv或或(1),iti titavv，则称，则称P是一条链接是一条链接的有向路的有向路1iitvv和 实际问题中实际问题中，如果，如果在图中赋予边一定的在图中赋予边一定的数量指标，我们常称之为数量指标，我们常称之为“权权”。通常。通常把把这种这种赋权图
16、赋权图称为网络。称为网络。与无向图和有向图相对应，网络又分为无与无向图和有向图相对应，网络又分为无向网络和有向网络。向网络和有向网络。三、网络三、网络 图的矩阵表示方法：图的矩阵表示方法：关联矩阵：关联矩阵：在图在图G=(V,E)G=(V,E)中，中，V=V=（v v1 1,v,v2 2,v vp p),),E E=(e=(e1 1,e,e2 2,e eq q)，见图，见图6.5,6.5,10ijijvea当点 与边 关联否则()ijp qAa构造一个矩阵构造一个矩阵 其中其中图图6.5则称则称A A为为G G的关联矩阵的关联矩阵。关联指顶点与边的关系。关联指顶点与边的关系。123456123
17、45110000101100010110001001000011eeeeeevvvvv图图6.5的关联矩阵的关联矩阵n邻接矩阵：邻接矩阵：在图在图G=(V,E)G=(V,E)中，中，V=V=（v v1 1,v,v2 2,v,vp p),),E E=(e=(e1 1,e,e2 2,e,eq q),),见图见图6.66.6()ij p qAa10ijijva当点 与边v 相邻否则构造一个构造一个矩阵矩阵 其中其中图图6.66.6则称则称A A为为G G的邻接矩阵的邻接矩阵。邻接指顶点与顶点的关系。邻接指顶点与顶点的关系。12345123450110010110110010100100110vvvv
18、vvvvvv图图6.66.6的邻接矩阵的邻接矩阵n权矩阵权矩阵 ：在图在图G=(V,E)G=(V,E)中，中，V=V=(v v1 1,v,v2 2,v,vp p),E=(e),E=(e1 1,e,e2 2,e,eq q),),其边其边 v vi i,v,vj j 有权有权w wijij。见图。见图6.76.7()ijpqAa0ijijijwvEa,v否则构造一个构造一个矩阵矩阵 其中其中图图6.76.7n则称则称A A为为G G的的权矩阵。权矩阵。12345123450740070260420030600500350vvvvvvvvvv图图6.76.7的权矩阵的权矩阵6.2 6.2 树树a）b
19、）已知已知用点用点 分别表示分别表示 5 5个城个城市。如果在市。如果在v v1 1与与v v5 5，v v1 1与与v v2 2，v v3 3与与v v4 4之间之间各架一条电话线，这个方案可用各架一条电话线，这个方案可用图图6.76.7（a a）表示出来。这个方案显然是不满足）表示出来。这个方案显然是不满足要求的，因为在这样的电话线网中，要求的，因为在这样的电话线网中，v v3 3，v v4 4与与v v1 1，v v2 2，v v5 5之间就不能通话之间就不能通话。12345,vvvvv图图6.76.7（a a）如果按照图如果按照图 6.7（b）来设计电话网，）来设计电话网，虽然方案能满
20、足不同城市之间通话的要虽然方案能满足不同城市之间通话的要求，但却不能保证电话线的条数最少。求，但却不能保证电话线的条数最少。原因是图原因是图 中含有一个圈，中含有一个圈，如果从这个圈上，任意去掉一条，并不如果从这个圈上，任意去掉一条，并不影响电话网的连通性，同时又可节省一影响电话网的连通性，同时又可节省一条线。条线。因此，满足要求的电话网必须是：因此，满足要求的电话网必须是：连通的；不含圈的。满足这两点要求连通的；不含圈的。满足这两点要求的图称为的图称为“树树”。12345,v v v v v图图 6.7（b）6.2.1 6.2.1 树的基本概念与性质树的基本概念与性质定义定义：连通且不含圈的
21、无向图称为树。树中连通且不含圈的无向图称为树。树中次为次为1的顶点称为树叶的顶点称为树叶(悬挂点悬挂点)，次大于，次大于 1的的顶点称为分枝点。顶点称为分枝点。树的性质可用下面定理给出树的性质可用下面定理给出：设有图设有图G=(V,E)G=(V,E)，n n和和m m分别为图分别为图G G的顶点数和的顶点数和边数，则下列命题是等价的：边数，则下列命题是等价的：n（1 1）G G是一个树。是一个树。n（2 2）G G无圈，且无圈，且m=n-1 m=n-1。n（3 3）G G连通，且连通，且m=n-1 m=n-1。n（4 4）G G无圈，但每加一条新边即存在唯一一个无圈，但每加一条新边即存在唯一一
22、个圈。圈。n（5 5）G G 连通，但每舍去一条边就变成不连通。连通，但每舍去一条边就变成不连通。n（6 6）G G中任意两点，有唯一路相连。中任意两点，有唯一路相连。定义定义6-7 图图G=(V,E)G=(V,E)，若若EE是是E E的子集，的子集，VV是是V V的子集，且的子集，且EE中的边仅与中的边仅与VV中的顶点中的顶点相关联，则称相关联，则称G=(V,E)G=(V,E)是是G G的一个子的一个子图。特别的，若图。特别的，若V=VV=V，则则GG称为称为G G的生成的生成子图子图（或支撑子图）（或支撑子图）定义定义6-8 若图若图G G的生成子图是一棵树，则称的生成子图是一棵树，则称该
23、树为该树为G G的生成树，或简称为的生成树，或简称为图图G G的树的树。G G中中属于生成树的边称为属于生成树的边称为树枝树枝，不在生成树中，不在生成树中的边称为的边称为弦。弦。定理定理 6-4 证明：必要性由定义直接可得。证明：必要性由定义直接可得。充分性的证明过程如下：充分性的证明过程如下：设图设图G G是连通的。若是连通的。若G G不含圈，则不含圈，则 G G就是其自就是其自身的一棵生成树；身的一棵生成树；若若G G含有圈，任取一个圈，从圈中任意去掉含有圈，任取一个圈，从圈中任意去掉一条边，得到图一条边，得到图G G的一个生成子图的一个生成子图G G1 1。如果如果G G1 1不含圈，那
24、么不含圈，那么G G1 1是是G G的一棵生成的一棵生成树；树；如果如果G G1 1仍含有圈，那么从仍含有圈，那么从G G1 1中任取一个中任取一个圈，从圈中再任意去掉一条边，得到图圈，从圈中再任意去掉一条边，得到图 G G的一个生成子图的一个生成子图G G2 2。重复使用此法使每个圈都受到破坏，重复使用此法使每个圈都受到破坏，最后可以得到最后可以得到G G的一个生成子图的一个生成子图G Gk k，它是不，它是不含圈的生成子图。含圈的生成子图。这就是这就是G G一棵生成树。一棵生成树。n上述上述充分性的证明给出了求生成树的一充分性的证明给出了求生成树的一种方法。就是任取一个圈，从圈中去掉种方法
25、。就是任取一个圈，从圈中去掉一边，对余下的图重复这个步骤，直到一边，对余下的图重复这个步骤，直到不含圈时为止，即得到一棵生成树，称不含圈时为止，即得到一棵生成树，称这种方法为这种方法为“破圈法破圈法”。n除除“破圈法破圈法”外，还有另一种方法可称外，还有另一种方法可称为为“避圈法避圈法”。这种方法是在图。这种方法是在图 G G中，中，每步选取一条边使它与已选边不构成圈，每步选取一条边使它与已选边不构成圈，直到选够直到选够n-1n-1条边为止。条边为止。6.2.2 6.2.2 最小支撑树及其算法最小支撑树及其算法（1）构造支撑树的）构造支撑树的算法算法1)破圈法 破破圈法思路：圈法思路：将连通有
26、圈图逐步删除边，变成将连通有圈图逐步删除边，变成连通连通无圈图。无圈图。l破圈法步骤：破圈法步骤：G=(V,E)为连通图，为连通图，Gk=(V,Ek)是是G的支的支 撑子图。撑子图。步骤步骤1 开始取开始取G0=(V,E)=G，k=0 步骤步骤2 若若Gk不含圈，则不含圈，则Gk为支撑树；若为支撑树；若Gk含圈，取含圈，取Gk中的任一圈，去掉圈上任一条边，中的任一圈，去掉圈上任一条边，得得Gk+1=(V，Ek+1)，Ek+1=Ekek;步骤步骤3 若若kq(G)-p(G)+1,则重复步骤则重复步骤 2；否；否则，则，Gk+1一定是支撑树。一定是支撑树。2）避圈法避圈法 避避圈法思路：圈法思路：
27、将不连通的无圈图通过将不连通的无圈图通过边的增加，逐步变成连边的增加，逐步变成连 通通无圈图。无圈图。避圈法步骤：避圈法步骤：为连通图。为连通图。步骤步骤1 1 始取始取 ；步骤步骤 2 2 若若G Gk k 连通，则连通，则G Gk k为支撑树；若为支撑树；若G Gk k不不连通，任选图连通，任选图G G边集边集E E中的一边中的一边e e，使，使e e的的两个端点分属两个不同的连通分图，两个端点分属两个不同的连通分图，得，得，；步骤步骤 3 3 若若 ，则重复步骤，则重复步骤 2 2；否则，否则，G Gk k一定是支撑树。一定是支撑树。(,)GVE0(,),0GVk111(,),1kkkk
28、kGV EEEekk()1kp G支撑支撑树的构造不涉及边的权。将支撑树的构造不涉及边的权。将支撑树的构造与边权的选择结合，产生最小树的构造与边权的选择结合，产生最小树的概念。树的概念。最小最小支撑树支撑树是网络优化中一个重要的是网络优化中一个重要的概念，它在交通网、电话网、管道网、概念，它在交通网、电话网、管道网、电力网等设计中均有广泛的应用。电力网等设计中均有广泛的应用。n（2 2）最小支撑树定义）最小支撑树定义设有一个连通图设有一个连通图G G=(=(V V,E E),),每一边每一边e e=v vi i,v vj j 有一个权有一个权w w(e e)=)=w wijij，如果是的，如果
29、是的一个支撑树，称中所有边的权之和为一个支撑树，称中所有边的权之和为支支撑树的权撑树的权，记为：，记为：如果支撑树如果支撑树T T*的权的权W W(T T*)是是G G的所有支的所有支撑树中权数最小的，则称撑树中权数最小的，则称T T*是是G G的最小支的最小支撑树（也称最小树），撑树（也称最小树），即即,()iijvvTw Tw*()m in():w Tw TTG是的 支 撑 树 寻找寻找最小支撑树也可以用上面介绍的最小支撑树也可以用上面介绍的破圈法和避圈法破圈法和避圈法，但要在舍边和增边时，但要在舍边和增边时，增加一些边的权数的限制增加一些边的权数的限制。1）破圈法）破圈法 步骤：步骤：从
30、图从图G中任取一圈，去掉这个圈中任取一圈，去掉这个圈中权数最大的一条边，得一支撑子图中权数最大的一条边，得一支撑子图G1。在在G1中再任取一圈，再去掉圈中权数最中再任取一圈，再去掉圈中权数最大的一条边，得大的一条边，得G2。如此继续下去，一。如此继续下去，一直到剩下的子图中不再含圈为止。该子直到剩下的子图中不再含圈为止。该子图图G1就是的最小支撑树就是的最小支撑树T*。n2 2）KruskalKruskal算法（避圈法）算法（避圈法）KruskalKruskal算法是算法是KruskalKruskal于于19561956年提出年提出的一个产生最小树的算法的一个产生最小树的算法 算法的基本思想是
31、：算法的基本思想是：每次将一条权最每次将一条权最小的弧加入子图小的弧加入子图T T 中，并保证不形成圈。中，并保证不形成圈。即按照边长由小到大排序，如果当前弧加即按照边长由小到大排序，如果当前弧加入后不形成圈，则加入这条弧。当弧有入后不形成圈，则加入这条弧。当弧有 时，时，即为最小树。即为最小树。步骤步骤0 按照权的大小对边由小到大排序，按照权的大小对边由小到大排序，即即 令令 步骤步骤1 判断判断 是否含圈。如含圈，转步是否含圈。如含圈，转步骤骤2；否则，转步骤；否则，转步骤3.步骤步骤2 令令i=i+1。若。若im，转步骤，转步骤1；否；否则，结束，没有支撑树，则，结束，没有支撑树，G 不
32、联通。不联通。步骤步骤3 令令 。若。若j=n-1，结束，结束，T是最小树；否则，转步骤是最小树；否则，转步骤1。12()()()mwewewe1,0,ijT,1iTTejjn例例6-4 6-4 用用KruskalKruskal算法求解下算法求解下图图6.86.8（a)a)所示网络的最小树，所示网络的最小树，每条每条边上的数表示该边上的数表示该边的权值。边的权值。图图6.86.8（a)a)n解：解：按照破圈法的原则，从图中任取一圈，按照破圈法的原则，从图中任取一圈，去掉这个圈中权数最大的一条边，得一支去掉这个圈中权数最大的一条边，得一支撑子图。在支撑子图中再任取一圈，再去撑子图。在支撑子图中再
33、任取一圈，再去掉圈中权数最大的一条边。如此继续下去，掉圈中权数最大的一条边。如此继续下去，一直到剩下的子图中不再含圈为止。该子一直到剩下的子图中不再含圈为止。该子图就是所求的最小生成树。最小生成树如图就是所求的最小生成树。最小生成树如图图6.86.8（b b）所示：）所示：图图6.86.8（b b）3 3）PrimPrim算法算法(边割法边割法)PrimPrim算法又称为边割法算法又称为边割法，是，是PrimPrim于于19571957年提出的求解最小树的算法年提出的求解最小树的算法。算法的核心思想是算法的核心思想是不断扩展一个不断扩展一个子树子树，使其逐步包含所有的顶点。具，使其逐步包含所有
34、的顶点。具体增边的选择，是在当前子树的顶点体增边的选择，是在当前子树的顶点集合与补集合所形成的边割中选择最集合与补集合所形成的边割中选择最小的边小的边。nPrimPrim算法：算法：步骤步骤0 0 从图中任选从图中任选一点一点ViVi，让让ViViS S，图，图中其余点均包含在中其余点均包含在 中中；步骤步骤2 2 从从 之间的连线中找出最小之间的连线中找出最小边，这条边一定包含在边，这条边一定包含在 最小最小支撑树内，不支撑树内，不妨设最小边为妨设最小边为 v vi,i,v vj j，将，将 v vi,i,v vj j 标记标记成最成最小小支撑树内的边；支撑树内的边；SS和S步骤步骤3 3
35、令令 步骤步骤4 4 重复步骤重复步骤2 2、步骤、步骤3 3，一直到图中，一直到图中所有点均包含在所有点均包含在S S中为止。中为止。jjSvSSvS，n例题例题6-5 6-5 用用PrimPrim算法求解图算法求解图6.96.9（a a）中的最）中的最小树。小树。图图6.96.9（a a）n解：求解结果见图解：求解结果见图6.9（b）图图6.9（b）例例6-6-在一个地区有一个公共服务机构，在一个地区有一个公共服务机构，如飞机场、医院等，图如飞机场、医院等，图6 6.1010中中O O所示。三个所示。三个乡镇（图乡镇（图6.106.10中的中的v1,v2,v3v1,v2,v3所示）需要连所
36、示）需要连接到这个公共服务机构。乡镇与服务机构接到这个公共服务机构。乡镇与服务机构之间、乡镇与乡镇之间的连接高速公路的之间、乡镇与乡镇之间的连接高速公路的造价为边的权。造价为边的权。问如何构建这个连问如何构建这个连接网络并分配建设接网络并分配建设费用？费用？图图6.106.10解：解：这显然是一个最小支撑树的构建和建这显然是一个最小支撑树的构建和建设成本分担问题。设成本分担问题。n v1,v2,v3分别连接到分别连接到O的建设成本为的建设成本为C(v1)9，C(v2)10，C(v3)11；n 将将 v1,v2 连接到连接到O的最小树的建设成本为的最小树的建设成本为C(v1,v2)17，同样，同
37、样，C(v1,v3)18，C(v2,v3)11；n将将3个顶点连接到个顶点连接到 的最小树的最小树O的建设成本的建设成本C(v1,v2,v3)18 n设分别承担的建设费用为设分别承担的建设费用为x1,x2,x3，则建，则建设费用的分配应该满足：设费用的分配应该满足：n有无限个向量有无限个向量满足上式，每个满足上式，每个向量都可以作为一个建设费用的分配方向量都可以作为一个建设费用的分配方案。案。12312132312309,010,011;17,18,11;18xxxxxxxxxxxx6.3 6.3 最短路问题最短路问题 最短路问题是网络理论中应用最广泛最短路问题是网络理论中应用最广泛的问题之一
38、。许多优化问题可以使用这个的问题之一。许多优化问题可以使用这个模型，如设备更新、管道铺设、线路安排、模型，如设备更新、管道铺设、线路安排、厂区布局等。厂区布局等。在上一章中我们曾介绍了最短路问题在上一章中我们曾介绍了最短路问题的动态规划解法，但某些最短路问题（的动态规划解法，但某些最短路问题（如如道路不能整齐分段者道路不能整齐分段者）构造动态规划方程）构造动态规划方程比较困难，而图论方法则比较有效。另外，比较困难，而图论方法则比较有效。另外，这个问题相对比较简单，其算法经常做为这个问题相对比较简单，其算法经常做为其他问题的子算法而调用。其他问题的子算法而调用。最短路问题是求一条最短路问题是求一
39、条v v1 1v vj j的路的路 ，使它是从使它是从v v1 1到到v vj j的所有路中总权最小的路。的所有路中总权最小的路。即：优化问题即：优化问题6.3.1 基本概念与基本概念与Bellman方程方程 最短路问题最短路问题的一般提法是设的一般提法是设N=(V,A,W)N=(V,A,W)为网络图，图中各边为网络图，图中各边(v vi ,i ,v vj j)有权有权w wi ji j（w wijij=表示表示v vi,i,v vj j之间没有边），之间没有边），v v1 1为起为起始点，始点，v vj j为图中任意一点。网络中有多条为图中任意一点。网络中有多条v v1 1v vj j的路的
40、路P,P,每条路的权是其所有构成弧的每条路的权是其所有构成弧的权之和权之和。1,1,1,1m in():jjjjPw PPvv是的 路1,jP 对于网络中的一个圈，其权是其所构成对于网络中的一个圈，其权是其所构成边的权之和。权为正的圈称为边的权之和。权为正的圈称为正圈正圈；权为；权为负的圈称为负的圈称为负圈负圈；权为；权为0的圈称为的圈称为零圈零圈。在一个没有负圈的网络中，求解最短路在一个没有负圈的网络中，求解最短路问题比较简单，目前的大多数算法也是面问题比较简单，目前的大多数算法也是面向这种网络的。向这种网络的。对于存在负圈的网络，其最短路的求解对于存在负圈的网络，其最短路的求解问题很复杂，
41、目前还没有好的有效算法。问题很复杂，目前还没有好的有效算法。10 (6.1)m in,2,3,.,jkkjkjuB ellm anuuwjn方 程n定理定理 6-5 6-5 设有向网络设有向网络G G中只含正圈，并中只含正圈，并且从点且从点v v1 1到其余点到其余点 v vj j都有有限长度的有都有有限长度的有向路，那么向路，那么(6.1)(6.1)有唯一有限解。有唯一有限解。n定理定理 6-6 6-6 设设 不含圈，则不含圈，则N N的顶点的顶点可以重新编号可以重新编号，使，使,ijijvvA(,)NVABellmanBellman算法的基本思想是：算法的基本思想是：基于这样的事实：从基于
42、这样的事实：从v v1 1到到v vj j的最短路总的最短路总是沿着该路先到是沿着该路先到v vj j前面的某一点前面的某一点v vi i ，然后，然后再沿着再沿着(v(vi i ,v vj j)到到v vj j 。于是，若。于是，若v v1 1到到v vj j为最为最短路，则短路，则v v1 1到到v vj j亦为最短路。亦为最短路。例例6-7 6-7 计算计算如下网络中如下网络中 各点的最短路各点的最短路。图图6.116.11解：解：这是一个有圈网络图，但这是一个有圈网络图，但v v1 1是起始点，是起始点，故进入故进入v v1 1的弧可以删去。对顶点进行重新标的弧可以删去。对顶点进行重新
43、标号，得到网络图，图号，得到网络图，图6-11(b)6-11(b)。12223334445550,m inm in011,m inm in011,m inm in05,1(2),131,m inm in11,140iiiiiiiiiiiiuuuwuuwuuwuuw n按照按照u ui i，求出最短路网络，图，求出最短路网络，图6-11(c)6-11(c)。nBellmanBellman方程的计算：方程的计算：6.3.2 Dijkstra算法算法 1959 1959年年,E.W.DijkstraE.W.Dijkstra 提出了求正提出了求正权网络最短路径的标号法，用给节点记权网络最短路径的标号法
44、，用给节点记标号来逐步形成起点到各点的最短路径标号来逐步形成起点到各点的最短路径及其距离值，是目前较好的一种算法。及其距离值，是目前较好的一种算法。Dijkstra 算法也称为双标号法。算法也称为双标号法。也就是对图中的每个点也就是对图中的每个点vj 赋予两个参数（通赋予两个参数（通常称为标号）常称为标号）：第一个标号第一个标号uj表示从起点表示从起点v1到到vj的最短路的最短路的长度，是距离标号；的长度，是距离标号；第二个标号第二个标号 称作前趋标号，是称作前趋标号，是记录在记录在v1到到vj的最短路上，的最短路上，vj 前面一个邻点前面一个邻点的下标，用来标识最短路路径，从而可对终的下标，
45、用来标识最短路路径，从而可对终点到始点进行反向追踪，找到点到始点进行反向追踪，找到v1到到vj的最短的最短路。通过不断修改这些标号，进行迭代计算。路。通过不断修改这些标号，进行迭代计算。(,()jupredj()predjDijkstraDijkstra 算法：算法：步骤步骤0 0 给起点给起点v v1 1标号标号(0,s)(0,s)，表示从，表示从v v1 1到到v v1 1的距离为的距离为0 0，v vs s为起为起 点。点。S 步骤步骤1 1 如果如果S S=V V，则，则u uj j即为即为v v1 1到到v vj j的最短的最短路的长度，最短路可路的长度，最短路可以按照以按照 pre
46、dpred(j j)记记录的信息，反向追踪即可获得，结束。录的信息，反向追踪即可获得，结束。否则，转步骤否则，转步骤2。步骤步骤2 求出弧集求出弧集 。若若 ，表明从所有已经赋予标号的顶，表明从所有已经赋予标号的顶点出发，不再有这样的弧，它的另一顶点出发，不再有这样的弧，它的另一顶点尚未标号，则计算结束。对于已有标点尚未标号，则计算结束。对于已有标号的顶点，可求得从到达这个顶点的最号的顶点，可求得从到达这个顶点的最短路，对于没有标号的顶点，则不存在短路，对于没有标号的顶点，则不存在从到达这个顶点的路。从到达这个顶点的路。若弧集，转步骤若弧集，转步骤3。A (,)|,ijijAv vvS vS步
47、骤步骤3 3 对弧集对弧集A A中的每一条弧中的每一条弧(v vi,i,v vj j)，计算计算 则则v vi i 赋予双标号赋予双标号 其中其中 。转步骤转步骤 2 2min:,iijijiijuwvvAuw(,)juijii juuw jSSv 经上述一个循环的计算，将求出经上述一个循环的计算，将求出v v1 1到一到一个顶点个顶点v vj j的最短路及其长度，从而使一个顶的最短路及其长度，从而使一个顶点点v vj j得到双标号。得到双标号。若图中总共有若图中总共有n n个顶点，则最多计算个个顶点，则最多计算个(n n-1)-1)循环，即可得到最后结果。循环，即可得到最后结果。n例例6-8
48、 求求v1到其余各点的最短路到其余各点的最短路 图图6.12n解解：（1）给给起点起点V1 标号标号(0,S)，表示从表示从V1到到V1的距离的距离P(V1)=0,V1为为起点。起点。（2）标号标号点的点的集合集合 ，没标号点没标号点的的集合集合 ，弧集弧集 中中，点，点V2 对应的是对应的是010，点点V3对应对应的是的是015，点点V4对应对应的的是是08。点点V4最小最小，故，故点点V4得到得到双标号（双标号（8，1）。）。8代表代表从从V1到到V4的的最短路长度，最短路长度，1代表代表前趋前趋点点V1。1 Sv234567,Sv v v v v v234567,Svvvvvv:,iij
49、ijuwv vA（3）标号标号点的点的集合集合 ，没标号点的没标号点的集合集合 ，弧集，弧集 中点中点V2对应对应的是的是10，点点V3 对应的是对应的是15。点点V2最小最小，点点V2得到得到双标双标号（号（10，1）。）。10代表最短路长度，代表最短路长度，1代表代表前趋前趋点点V1。14,Sv v23567,Svvvvv:,iijijuwv vA1213(,)|,(,),(,)ijijAv vvS vSvvvv（4 4）标号标号点的集合点的集合 ，没标没标号点的号点的集合集合 ，弧，弧集集点点V3V3对应对应的是的是10102 2，点点V5V5对应对应的是的是10106 6。故故点点V3
50、V3得到得到双标号（双标号（1212，2 2）。）。124,Sv vv132325(,),(,),(,),(,)ijijAv vvS vSvvvvvv3567,Svvvvn（5）标号标号点的集合点的集合 ，没标没标号点的集合号点的集合 ，弧弧集集点点V5对应对应的仍然是的仍然是16，点点V5得到得到双标号双标号（16，2）。）。567,Svvv1234,Sv vvv25(,),(,)ijijAv vvS vSvv（6 6）标号标号的点的的点的集合集合 ，没标号的点的没标号的点的集合集合 ，弧弧集集点点V7V7对应对应的是的是16162020，点点V7V7得到得到双标号双标号（3636，5 5）
