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

《《图论模型：最短路》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图论模型：最短路》PPT课件.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、限非空点集，则称是有限非空点集，则称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,n),i,j=1,2,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入边。入边。由边连接的两个点称为相邻的点；有一个公共端点

4、的边称由边连接的两个点称为相邻的点；有一个公共端点的边称为相邻边；边和它的端点称为互相关联。常用为相邻边；边和它的端点称为互相关联。常用d(v)d(v)表示图表示图G G中与顶点中与顶点v v关联的边的数目，关联的边的数目，d(v)d(v)称为顶点称为顶点v v的度数；用的度数；用N N（v v）表示图）表示图G G中所有与顶点中所有与顶点v v相邻的顶点的集合。相邻的顶点的集合。定义定义22若将图若将图G G的每条边的每条边e e都对应一个实数都对应一个实数F(e)F(e)，则称，则称F F（e e）为该边的权，并称图为该边的权，并称图G G为赋权图，记为为赋权图，记为G=(V,E,F)G=

5、(V,E,F)。定义定义33设设G=(V,E)G=(V,E)是一个图，是一个图，则称是则称是G G的一个通路。如果通路中没有相同的边，则称此的一个通路。如果通路中没有相同的边，则称此通路为道路；始点和终点相同的道路称为圈或回路；如果通路为道路；始点和终点相同的道路称为圈或回路；如果通路中既没有相同的边，又没有相同的顶点，则称此通路通路中既没有相同的边，又没有相同的顶点，则称此通路为路径，简称路。为路径，简称路。定义定义44任意两点都有通路的图称为连通图。任意两点都有通路的图称为连通图。定义定义55连通而无圈的图称为树，常用连通而无圈的图称为树，常用T T表示树。表示树。7.2 7.2 最短路模

6、型及其算法最短路模型及其算法最短路问题是网络理论中应用最为广泛的问题之一，最短路问题是网络理论中应用最为广泛的问题之一，不少优化问题可化为这个模型。如管道的铺设、运不少优化问题可化为这个模型。如管道的铺设、运输网络的设计、线路安排、设备更新、厂区布局等。输网络的设计、线路安排、设备更新、厂区布局等。定义定义11设设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

7、,v)的的权或长度。权或长度。定义定义22若若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)是是G G中连接中连接u,vu,v的最短路径。的最短路径。根据上述定理，著名计算机专家狄克斯特拉根据上述定理，著名计算机专家狄克斯特拉（DijkstraDijkstra）给出了求）给出了求G G中某一点到其他各点最短中某一点到其他各点最短路径的算法路径的算法标号法：标号法：T T标号与标号与P P

8、标号。标号。T T标号为标号为试探性标号，试探性标号，P P标号为永久性标号。标号为永久性标号。给给v vi i点一个点一个P P标号时，表示从标号时，表示从v v0 0（起点）到点（起点）到点v vi i的最的最短路权，短路权，v vi i点的标号不再改变；给点的标号不再改变；给v vi i点一个点一个T T标号标号时，表示从时，表示从v v0 0到到v vi i的估计最短路权，是一种临时标的估计最短路权，是一种临时标号。凡没有得到号。凡没有得到P P标号的点都标有标号的点都标有T T标号。标号。算法每一步是把某一点的算法每一步是把某一点的T T标号改为标号改为P P标号，当终点标号，当终点

9、得到得到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）比较所有）比较所有T T标号

10、的点，把最小者改为标号的点，把最小者改为P P标号，标号，当存在两个以上最小时，可同时改为当存在两个以上最小时，可同时改为P P标号，若全部标号，若全部点均为点均为P P标号，则停止；标号，则停止；例例22求下图中求下图中V V0 0到其余各点的最短路。到其余各点的最短路。迭代次数迭代次数T(v0)T(v1)T(v2)T(v3)T(v4)T(v5)T(v6)T(v7)P标标号号10+20 0281+v03281+v3428+10+v1583 3+10+V46861011V577 71011V289 911V6911V7最短路最短路权权027136911父点父点v0v0v5v0v1v4V2v4

11、例例2(2(设备更新问题设备更新问题)某企业使用一种设备某企业使用一种设备,每年年初每年年初,企企业都要作出决定业都要作出决定,如果要继续使用旧的如果要继续使用旧的,;,;若购买一台新若购买一台新设备设备,要付购买费要付购买费.使制定一个使制定一个5 5年更新计划年更新计划,使总费用最使总费用最少少?已知设备每年年初的购买费分别为已知设备每年年初的购买费分别为:11,11,12,12,13,:11,11,12,12,13,使使用不同时间设备所需的维修费为用不同时间设备所需的维修费为:解：设解：设b bi i表示设备在第表示设备在第i i年年初的购买费，年年初的购买费，c ci i表示设备表示设

12、备使用使用ii年后的维修费，把这个问题化为求有向赋权图年后的维修费，把这个问题化为求有向赋权图G=G=（V,E,FV,E,F）中的最短路问题。）中的最短路问题。设备设备年年龄龄0112233445维维修修费费5681118 赋权图如上图所示，这样设备更新问题就变为：从赋权图如上图所示，这样设备更新问题就变为：从v v1 1到到v v6 6的最的最短路问题。由狄克斯特拉（短路问题。由狄克斯特拉（DijkstraDijkstra）算法列表如下：）算法列表如下：迭代次数迭代次数T(v1)T(v2)T(v3)T(v4)T(v5)T(v6)P标标号号10+V121622304159V2322304157

13、V34304153V454153V5653V6最短路最短路权权01622304153父点父点V1V1V1V1V1V3或或v4 计算结果表明：路径计算结果表明：路径v v1 1v v3 3v v6 6或或v v1 1v v4 4v v6 6为两条最短路径，为两条最短路径，路长均为路长均为5353。即第。即第1 1年、第年、第3 3年个购买一台新设备，或年个购买一台新设备，或第第1 1年、第年、第4 4年各购买一台新设备为最优决策。最小费年各购买一台新设备为最优决策。最小费用为用为53.53.例例33如下图表示某区域的交通网络，各条旁边所注的数字如下图表示某区域的交通网络，各条旁边所注的数字表示通

14、过该公路所估计行驶的时间（单位：小时）。试问表示通过该公路所估计行驶的时间（单位：小时）。试问S S到到T T估计至少要行驶多少小时？并写出最短路径。估计至少要行驶多少小时？并写出最短路径。解：狄克斯特拉（解：狄克斯特拉（DijkstraDijkstra）算法列表如下：）算法列表如下：迭代次数迭代次数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 4

15、3 36 63 35 59 9V V1 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 1 最短路模型还可以应用于中心选址问题。所谓中心选址问最短路模型还可以应用于中心选址问题。所谓中心选址问题就是在一个网络中选择一点，建立公用服务设施，为该题就是在一个网络中选择一点，建立公用服务设施，为该网络中的客户提供服务，使得服务效率最高。比如一个区网络中的客户提供服务，使得

16、服务效率最高。比如一个区域的消防站、自来水厂、学校、变电站、银行商店等选址。域的消防站、自来水厂、学校、变电站、银行商店等选址。为了提高服务效率，自然的想法是将为了提高服务效率，自然的想法是将 这些设施建立在中心这些设施建立在中心地点。对于规则的网络，例如圆形、矩形等，中心地点是地点。对于规则的网络，例如圆形、矩形等，中心地点是显而易见的，然而对于更多的网络是不规则的。应此，我显而易见的，然而对于更多的网络是不规则的。应此，我们引入两个定义。们引入两个定义。例例44教育部们打算在某新建城区建一所学校教育部们打算在某新建城区建一所学校,让附近七个居让附近七个居民区的学生就近入学。七个居民区之间的

17、道路如下图所示民区的学生就近入学。七个居民区之间的道路如下图所示.学校应建在哪个居民区，学校应建在哪个居民区，才能使大家都方便？才能使大家都方便？（图中距离单位：百米）（图中距离单位：百米）解：由狄克斯特拉（解：由狄克斯特拉（DijkstraDijkstra）算法计算得各居民之间的最短距离列表如下算法计算得各居民之间的最短距离列表如下:ABCDEFG d(vd(vi i)di,jA034578101037B3032457724C4305568831D52502355(min)22(min)E7452013722(min)F8563102825G107853201035 从上表来看，应选择从上表

18、来看，应选择D D作为学校的地址，这样最远的作为学校的地址，这样最远的居民区离学校的距离也只有居民区离学校的距离也只有500500米米.在现实生活中，同一网络中的各点要求提供的服务的在现实生活中，同一网络中的各点要求提供的服务的数量也不尽数量也不尽 相同。我们将各点要求提供的服务数量相同。我们将各点要求提供的服务数量作为该点的权数，重新考虑选址问题。作为该点的权数，重新考虑选址问题。例例55在例在例4 4中，若七个区的学生人数分别为中，若七个区的学生人数分别为4040、2525、4545、3030、2020、3535、5050人，试问教育部门应将学校建在人，试问教育部门应将学校建在哪个居民区，

19、才能使大家都方便？哪个居民区，才能使大家都方便？所以应选择所以应选择E E作为新建学校的地址。作为新建学校的地址。ABCDEFGA0751801501402805001325B12001356080175350920C1607501501002104001095D20050225040105250870E28010022560035150850（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的最短路及长度的最短路及长度.图1图2