图论模型：最短路课件.ppt

1、第六章第六章 图论方法图论方法 7.1 7.1 图论的基本概念图论的基本概念 定义定义1 1 一个有序二元组（一个有序二元组（V,EV,E）称为一个图，记为）称为一个图，记为G=G=（V,EV,E），其中），其中 V V称为称为G G的顶点集，的顶点集，V V，V V中的元中的元素称为顶点或结点，简称点；素称为顶点或结点，简称点；E E称为称为G G的边集，其的边集，其元素称为边，它连接元素称为边，它连接V V中的两个点，如果这两个点是中的两个点，如果这两个点是无序的，则称该边为无向边；否则，称为有向边。无序的，则称该边为无向边；否则，称为有向边。如果如果V Vv v1 1,v,v2 2,v,

2、vn n 是有限非空点集，则称是有限非空点集，则称G G为有为有限图或限图或n n阶图。阶图。如果如果G G的每条边都是无向边，则称的每条边都是无向边，则称G G为无向图；如果为无向图；如果G G的每条边都是有向边，则称的每条边都是有向边，则称G G为有向图。否则称为有向图。否则称G G为混为混合图。并且常记合图。并且常记E Eee1 1,e,e2 2,e,em m,(e(ek k=v=vi iv vj j,i,j=1,2,i,j=1,2,n),n),对于一个图对于一个图G=G=（V,EV,E），人们通常用一个图形来表示，），人们通常用一个图形来表示，称其为图解。凡是有向图，在图解上用箭头标明

3、其方称其为图解。凡是有向图，在图解上用箭头标明其方向。向。则则G G（V,EV,E）是一个有）是一个有4 4个顶点、个顶点、6 6条边的图，其图条边的图，其图解如下图：解如下图：一个图会有许多外形不同的图解，如上图。一个图会有许多外形不同的图解，如上图。称点称点v vi i,v,vj j为边为边v vi iv vj j的端点。在有向图中，称点的端点。在有向图中，称点v vi i,v,vj j分别为有向边分别为有向边v vi iv vj j的始点和终点；称边的始点和终点；称边v vi iv vj j为点为点v vi i的出边，为点的出边，为点v vj j入边。入边。,V 434232413121

4、4321vvvvvvvvvvvvEvvvv，设设例例如如 e 6 e 2 e 3 e 5 e 4 e 1 v 3 v 1 v 2 v 4 e5e6e2e1e3e4v3v4v1v2 由边连接的两个点称为相邻的点；有一个公共端点的边称由边连接的两个点称为相邻的点；有一个公共端点的边称为相邻边；边和它的端点称为互相关联。常用为相邻边；边和它的端点称为互相关联。常用d(v)d(v)表示图表示图G G中与顶点中与顶点v v关联的边的数目，关联的边的数目，d(v)d(v)称为顶点称为顶点v v的度数；用的度数；用N N（v v）表示图）表示图G G中所有与顶点中所有与顶点v v相邻的顶点的集合。相邻的顶点

5、的集合。定义定义2 2 若将图若将图G G的每条边的每条边e e都对应一个实数都对应一个实数F(e)F(e)，则称，则称F F（e e）为该边的权，并称图为该边的权，并称图G G为赋权图，记为为赋权图，记为G=(V,E,F)G=(V,E,F)。定义定义3 3 设设G=(V,E)G=(V,E)是一个图，是一个图，则称是则称是G G的一个通路。如果通路中没有相同的边，则称此的一个通路。如果通路中没有相同的边，则称此通路为道路；始点和终点相同的道路称为圈或回路；如果通路为道路；始点和终点相同的道路称为圈或回路；如果通路中既没有相同的边，又没有相同的顶点，则称此通路通路中既没有相同的边，又没有相同的顶

6、点，则称此通路为路径，简称路。为路径，简称路。定义定义4 4 任意两点都有通路的图称为连通图。任意两点都有通路的图称为连通图。定义定义5 5 连通而无圈的图称为树，常用连通而无圈的图称为树，常用T T表示树。表示树。EvvkiVvvvviik1210,1,且 7.2 7.2 最短路模型及其算法最短路模型及其算法 最短路问题是网络理论中应用最为广泛的问题之一，最短路问题是网络理论中应用最为广泛的问题之一，不少优化问题可化为这个模型。如管道的铺设、运不少优化问题可化为这个模型。如管道的铺设、运输网络的设计、线路安排、设备更新、厂区布局等。输网络的设计、线路安排、设备更新、厂区布局等。定义定义1 1

7、 设设P P（u,vu,v）是赋权图）是赋权图G=(V,E,F)G=(V,E,F)中从点中从点u u到点到点v v的路径，用的路径，用E(P)E(P)表示路径表示路径P(u,v)P(u,v)的全部边的集合，的全部边的集合，记为，记为，则称，则称F(P)F(P)为路径为路径P(u,v)P(u,v)的的权或长度。权或长度。定义定义2 2 若若P P0 0(u,v)(u,v)是是G G中连接中连接u,vu,v的路径，且对任意在的路径，且对任意在G G中连接中连接u,vu,v的路径的路径P(u,v)P(u,v)，都有，都有F(P0)F(P),F(P0)F(P),则称则称P0(u,v)P0(u,v)是是

8、G G中连接中连接u,vu,v的最短路径。的最短路径。E(P)eF(e)F(P)根据上述定理，著名计算机专家狄克斯特拉根据上述定理，著名计算机专家狄克斯特拉（DijkstraDijkstra）给出了求）给出了求G G中某一点到其他各点最短中某一点到其他各点最短路径的算法路径的算法标号法：标号法：T T标号与标号与P P标号。标号。T T标号为标号为试探性标号，试探性标号，P P标号为永久性标号。标号为永久性标号。给给v vi i点一个点一个P P标号时，表示从标号时，表示从v v0 0（起点）到点（起点）到点v vi i的的最短路权，最短路权，v vi i点的标号不再改变；给点的标号不再改变；

9、给v vi i点一个点一个T T标标号时，表示从号时，表示从v v0 0到到v vi i的估计最短路权，是一种临时的估计最短路权，是一种临时标号。凡没有得到标号。凡没有得到P P标号的点都标有标号的点都标有T T标号。标号。.1,G 310210的父点的父点为为，称，称的最短路，则对的最短路，则对到到中从中从是是设设定义定义kkmmvvmkkvvvvvv.G,1,G 10210的最短路的最短路到到中从中从必为必为的最短路，则对的最短路，则对到到中从中从是是若若定理定理jijiimkvvvvvmjijivvvvvv 算法每一步是把某一点的算法每一步是把某一点的T T标号改为标号改为P P标号，当

10、终点标号，当终点得到得到P P标号时全部计算结束。其具体步骤如下：标号时全部计算结束。其具体步骤如下：（1 1）赋初值：给起点）赋初值：给起点v v0 0以以P P标号，标号，P(vP(v0 0)0 0，其余，其余各点各点v vi i均为均为T T标号标号,T,T（v vi i）+；（2 2）更新所有的）更新所有的T T标号：若标号：若v vi i点为刚得到的点为刚得到的P P标号的标号的点点,考虑这样的点考虑这样的点v vj j，边，边v vi iv vj jEE，且，且v vj j为为T T标号，对标号，对v vj j的的T T标号进行如下的更改：标号进行如下的更改：（3 3）比较所有）比

11、较所有T T标号的点，把最小者改为标号的点，把最小者改为P P标号，标号，当存在两个以上最小时，可同时改为当存在两个以上最小时，可同时改为P P标号，若全标号，若全部点均为部点均为P P标号，则停止；标号，则停止；.,)(),(min)(的的权权数数为为边边jiijjiijjvvffvPvTvT)(min)P(v*jjvT即：即：.2,*）转回（转回（代替代替否则，用否则，用ijvv 例例2 2 求下图中求下图中V V0 0到其余各点的最短路。到其余各点的最短路。.7,2,1,)T(T,0)P(P)1(00ivvvi标号，标号，其余各点为其余各点为标号，标号，以以首先给首先给解：解：28267

12、1951368431V0V1V3V2V4V5V7V6220,min)(),(min)(01011fvPvTvT880,min)(),(min)(02022fvPvTvT110,min)(),(min)(03033fvPvTvT.T,)2(321302010的标号的标号标号，所以修正这些点标号，所以修正这些点为为且且由于边由于边vvvEvvvvvv;1)(P)(TT)3(33vv 最小，所以令：最小，所以令：标号，标号，比较所有的比较所有的 :,P)4(3263233vvvvvvv的端点的端点标号的点，考察边标号的点，考察边为刚得到为刚得到2)(P)(TT)5(11vv 最小，所以令最小，所以令

13、标号，标号，比较所有比较所有871,8min)(),(min)(32322fvPvTvT991,min)(),(min)(36366fvPvTvT2)(1vT862,8min)(),(min)(12122fvPvTvT312,min)(),(min)(14144fvPvTvT:,P)6(4241211vvvvvvv的端点的端点标号的点，考察边标号的点，考察边为刚得到为刚得到9)(T6v282671951368431V0V1V3V2V4V5V7V6 ;3)(P)(TT)7(44vv 最小，所以令最小，所以令标号，标号，比较所有比较所有:,P)8(7527454244vvvvvvvvvv的端点的端

14、点考察边考察边标号的点标号的点为刚得到为刚得到;6)(P)(TT)9(55vv 最小，所以令最小，所以令标号，标号，比较所有比较所有853,8min)(),(min)(42422fvPvTvT633,min)(),(min)(45455fvPvTvT1183,min)(),(min)(47477fvPvTvT9)(6vT:,P)10(7627565255vvvvvvvvvv的端点的端点标号的点，考察边标号的点，考察边为刚得到为刚得到 ;7)(P)(TT)11(22vv 最小，所以令最小，所以令标号，标号，比较所有比较所有716,8min)(),(min)(52522fvPvTvT1046,10

15、min)(),(min)(56566fvPvTvT1166,11min)(),(min)(57577fvPvTvT:,P)12(6622vvvv的端点的端点考察边考察边标号的点标号的点为刚得到为刚得到927,10min)(),(min)(26266fvPvTvT11)(7vT1139,11min)(),(min)()13(67677fvPvTvT11)(7vP 9)(6vP 迭代次数迭代次数T(v0)T(v1)T(v2)T(v3)T(v4)T(v5)T(v6)T(v7)P标号标号10+2281+v03281+v3428+10+v1583 3+10+V46861011V577 71011V289

16、 911V6911V7最短路权最短路权027136911父点父点v0v0v5v0v1v4V2v4 2211381V0V1V3V2V4V5V7V6 例例2(2(设备更新问题设备更新问题)某企业使用一种设备某企业使用一种设备,每年年初每年年初,企企业都要作出决定业都要作出决定,如果要继续使用旧的如果要继续使用旧的,;,;若购买一台若购买一台新设备新设备,要付购买费要付购买费.使制定一个使制定一个5 5年更新计划年更新计划,使总费使总费用最少用最少?已知设备每年年初的购买费分别为已知设备每年年初的购买费分别为:11,11,12,12,13,:11,11,12,12,13,使用不同时间设备所需的维修费

17、为使用不同时间设备所需的维修费为:解：设解：设b bi i表示设备在第表示设备在第i i年年初的购买费，年年初的购买费，c ci i表示设备表示设备使用使用 i i年后的维修费，把这个问题化为求有向赋权图年后的维修费，把这个问题化为求有向赋权图G=G=（V,E,FV,E,F）中的最短路问题。）中的最短路问题。设备年龄设备年龄0112233445维修费维修费5681118165941161722231718302341302231v1v2v3v4v6v5 赋权图如上图所示，这样设备更新问题就变为：从赋权图如上图所示，这样设备更新问题就变为：从v v1 1到到v v6 6的最的最短路问题。由狄克斯

18、特拉（短路问题。由狄克斯特拉（DijkstraDijkstra）算法列表如下：）算法列表如下：.)F(6,ji,1E.,6654321ijikkijijiicbvvvvvivvvvvvvV表示第五年年底表示第五年年底个点个点，虚设一，虚设一年年初购进一台新设备年年初购进一台新设备表示第表示第迭代次数迭代次数T(v1)T(v2)T(v3)T(v4)T(v5)T(v6)P标号标号10+V121622304159V2322304157V34304153V454153V5653V6最短路权最短路权01622304153父点父点V1V1V1V1V1V3或或v4 计算结果表明：路径计算结果表明：路径v v

19、1 1v v3 3v v6 6或或v v1 1v v4 4v v6 6为两条最短路径，为两条最短路径，路长均为路长均为5353。即第。即第1 1年、第年、第3 3年个购买一台新设备，年个购买一台新设备，或第或第1 1年、第年、第4 4年各购买一台新设备为最优决策。最年各购买一台新设备为最优决策。最小费用为小费用为53.53.例例3 3 如下图表示某区域的交通网络，各条旁边所注的数如下图表示某区域的交通网络，各条旁边所注的数字表示通过该公路所估计行驶的时间（单位：小时）。字表示通过该公路所估计行驶的时间（单位：小时）。试问试问S S到到T T估计至少要行驶多少小时？并写出最短路径。估计至少要行驶

20、多少小时？并写出最短路径。解：狄克斯特拉（解：狄克斯特拉（DijkstraDijkstra）算法列表如下：）算法列表如下：42157415523154311SV1TV6V3V2V4V5 42157415523154311SV1TV6V3V2V4V5迭代次数迭代次数 T T（S S）T(VT(V1 1)T(VT(V2 2)T(VT(V3 3)T T（V V4 4）T T（V V5 5）T T（V V6 6）T T（T T）P P标号标号1 10 0+S S2 24 4+1 1+4 45 5+V V3 33 33 32 26 63 35 5+V V2 2 4 43 36 63 35 59 9V V

21、1 1 5 56 63 35 57 7V V5 56 66 65 57 7V V6 6 7 76 67 7V V4 4 8 87 7D D最短路权最短路权0 03 32 21 16 63 35 57父点父点S S V V3 3V V3 3S SV V3 3V V3 3S SV V1 17.DS13，最最短短距距离离为为的的最最短短路路径径为为：到到从从DVVS 最短路模型还可以应用于中心选址问题。所谓中心选址问最短路模型还可以应用于中心选址问题。所谓中心选址问题就是在一个网络中选择一点，建立公用服务设施，为该题就是在一个网络中选择一点，建立公用服务设施，为该网络中的客户提供服务，使得服务效率最

22、高。比如一个区网络中的客户提供服务，使得服务效率最高。比如一个区域的消防站、自来水厂、学校、变电站、银行商店等选址。域的消防站、自来水厂、学校、变电站、银行商店等选址。为了提高服务效率，自然的想法是将为了提高服务效率，自然的想法是将 这些设施建立在中心这些设施建立在中心地点。对于规则的网络，例如圆形、矩形等，中心地点是地点。对于规则的网络，例如圆形、矩形等，中心地点是显而易见的，然而对于更多的网络是不规则的。应此，我显而易见的，然而对于更多的网络是不规则的。应此，我们引入两个定义。们引入两个定义。).,2,1,0,N,21njidvvdvvvniijijin（即最短路长度），（即最短路长度），

23、之间的距离之间的距离到到表示点表示点个点：个点：有有设网络设网络.I,)(),(min,max)(11,1为直径为直径为网络的中心，为网络的中心，点点则称则称若若：记：记定义定义kkinijinjivIvdvdIdvd 例例4 4 教育部们打算在某新建城区建一所学校教育部们打算在某新建城区建一所学校,让附近七个居让附近七个居民区的学生就近入学。七个居民区之间的道路如下图所示民区的学生就近入学。七个居民区之间的道路如下图所示.学校应建在哪个居民区，学校应建在哪个居民区，才能使大家都方便？才能使大家都方便？（图中距离单位：百米）（图中距离单位：百米）解：由狄克斯特拉（解：由狄克斯特拉（Dijkst

24、raDijkstra）算法计算得各居民之间的最短距离列表如下算法计算得各居民之间的最短距离列表如下:7234324615724ABDCEFGABCDEFG d(vd(vi i)di,jA034578101037B3032457724C4305568831D52502355(min)22(min)E7452013722(min)F8563102825G107853201035 从上表来看，应选择从上表来看，应选择D D作为学校的地址，这样最远的作为学校的地址，这样最远的居民区离学校的距离也只有居民区离学校的距离也只有500500米米.在现实生活中，同一网络中的各点要求提供的服务在现实生活中，同一

25、网络中的各点要求提供的服务的数量也不尽的数量也不尽 相同。我们将各点要求提供的服务数相同。我们将各点要求提供的服务数量作为该点的权数，重新考虑选址问题。量作为该点的权数，重新考虑选址问题。例例5 5 在例在例4 4中，若七个区的学生人数分别为中，若七个区的学生人数分别为4040、2525、4545、3030、2020、3535、5050人，试问教育部门应将学校建人，试问教育部门应将学校建在哪个居民区，才能使大家都方便？在哪个居民区，才能使大家都方便？.),()(min),2,1()(),(211,为为网网络络的的重重心心则则称称点点若若令令点点的的权权为为：设设定定义义kkininjjiiii

26、iivvhvhnidfvhvffv 所以应选择所以应选择E E作为新建学校的地址。作为新建学校的地址。71,)(jjiiidfvhABCDEFGA0751801501402805001325B12001356080175350920C1607501501002104001095D20050225040105250870E28010022560035150850（min）F32012527090200100925G400175360150607001215 练习题练习题1 1、准备在、准备在A A，B B，C C，D D，E E，F F，G G七个居民点中七个居民点中建一个剧场，各个居民点之间的距离和联系如建一个剧场，各个居民点之间的距离和联系如下图下图1 1所示，问剧场应建在那一个居民点，使各所示，问剧场应建在那一个居民点，使各点到剧场的距离之和为最小？点到剧场的距离之和为最小？2 2、求上图、求上图2 2中从点中从点v v1 1到到v v8 8的最短路及长度的最短路及长度.64321.52.51.831.5V5V3V4V2V6V1V72866992172142V1V3V2V4V5V7V6V8图1图2