图论模型最短路精品文稿.ppt

图论模型最短路第1页，本讲稿共22页7.1 7.1 图论的基本概念图论的基本概念定义定义1 1 一个有序二元组（一个有序二元组（V,EV,E）称为一个图，记为）称为一个图，记为G=G=（V,EV,E），），其中其中 V V称为称为G G的顶点集，的顶点集，VV，V V中的元素称为顶点或中的元素称为顶点或结点，简称点；结点，简称点；E E称为称为G G的边集，其元素称为边，它连的边集，其元素称为边，它连接接V V中的两个点，如果这两个点是无序的，则称该边为无向中的两个点，如果这两个点是无序的，则称该边为无向边；否则，称为有向边。边；否则，称为有向边。如果如果V Vv v1 1,v,v2 2,v,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），人们通常用一个图形来表示，称其为），人们通常用一个图形来表示，称其为图解。凡是有向图，在图解上用箭头标明其方向。图解。凡是有向图，在图解上用箭头标明其方向。第2页，本讲稿共22页 则则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入边。入边。第3页，本讲稿共22页 由边连接的两个点称为相邻的点；有一个公共端点的边称为相由边连接的两个点称为相邻的点；有一个公共端点的边称为相邻边；边和它的端点称为互相关联。常用邻边；边和它的端点称为互相关联。常用d(v)d(v)表示图表示图G G中与顶点中与顶点v v关联的边的数目，关联的边的数目，d(v)d(v)称为顶点称为顶点v v的度数；用的度数；用N N（v v）表示图）表示图G G中中所有与顶点所有与顶点v v相邻的顶点的集合。相邻的顶点的集合。定义定义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的一个通路。如果通路中没有相同的边，则称此通路为道的一个通路。如果通路中没有相同的边，则称此通路为道路；始点和终点相同的道路称为圈或回路；如果通路中既没有相路；始点和终点相同的道路称为圈或回路；如果通路中既没有相同的边，又没有相同的顶点，则称此通路为路径，简称路。同的边，又没有相同的顶点，则称此通路为路径，简称路。定义定义4 4 任意两点都有通路的图称为连通图。任意两点都有通路的图称为连通图。定义定义5 5 连通而无圈的图称为树，常用连通而无圈的图称为树，常用T T表示树。表示树。第4页，本讲稿共22页 7.2 7.2 最短路模型及其算法最短路模型及其算法最短路问题是网络理论中应用最为广泛的问题之一，最短路问题是网络理论中应用最为广泛的问题之一，不少优化问题可化为这个模型。如管道的铺设、运不少优化问题可化为这个模型。如管道的铺设、运输网络的设计、线路安排、设备更新、厂区布局等。输网络的设计、线路安排、设备更新、厂区布局等。定义定义1 1 设设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)是是G G中连接中连接u,vu,v的最短路径。的最短路径。第5页，本讲稿共22页 根据上述定理，著名计算机专家狄克斯特拉根据上述定理，著名计算机专家狄克斯特拉（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点的标号不再改变；给点的标号不再改变；给v vi i点一个点一个T T标号标号时，表示从时，表示从v v0 0到到v vi i的估计最短路权，是一种临时标的估计最短路权，是一种临时标号。凡没有得到号。凡没有得到P P标号的点都标有标号的点都标有T T标号。标号。第6页，本讲稿共22页 算法每一步是把某一点的算法每一步是把某一点的T T标号改为标号改为P P标号，当终点得到标号，当终点得到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标号的点，把最小者改为标号的点，把最小者改为P P标号，标号，当存在两个以上最小时，可同时改为当存在两个以上最小时，可同时改为P P标号，若全部点均标号，若全部点均为为P P标号，则停止；标号，则停止；第7页，本讲稿共22页 例例2 2 求下图中求下图中V V0 0到其余各点的最短路。到其余各点的最短路。第8页，本讲稿共22页 第9页，本讲稿共22页 第10页，本讲稿共22页 第11页，本讲稿共22页 迭代次数迭代次数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第12页，本讲稿共22页 第13页，本讲稿共22页 例例2(2(设备更新问题设备更新问题)某企业使用一种设备某企业使用一种设备,每年年初每年年初,企业都要企业都要作出决定作出决定,如果要继续使用旧的如果要继续使用旧的,;,;若购买一台新设备若购买一台新设备,要付购要付购买费买费.使制定一个使制定一个5 5年更新计划年更新计划,使总费用最少使总费用最少?已知设备每年年初的购买费分别为已知设备每年年初的购买费分别为:11,11,12,12,13,:11,11,12,12,13,使用不同使用不同时间设备所需的维修费为时间设备所需的维修费为:解：设解：设b bi i表示设备在第表示设备在第i i年年初的购买费，年年初的购买费，c ci i表示设备使用表示设备使用 i i年后的维修费，把这个问题化为求有向赋权图年后的维修费，把这个问题化为求有向赋权图G=G=（V,E,FV,E,F）中的最短路问题。）中的最短路问题。设备设备年年龄龄0112233445维维修修费费5681118第14页，本讲稿共22页 赋权图如上图所示，这样设备更新问题就变为：从赋权图如上图所示，这样设备更新问题就变为：从v v1 1到到v v6 6的最短路问的最短路问题。由狄克斯特拉（题。由狄克斯特拉（DijkstraDijkstra）算法列表如下：）算法列表如下：迭代次数迭代次数T(v1)T(v2)T(v3)T(v4)T(v5)T(v6)P标标号号10+V121622304159V2322304157V34304153V454153V5653V6最短路最短路权权01622304153父点父点V1V1V1V1V1V3或或v4第15页，本讲稿共22页 计算结果表明：路径计算结果表明：路径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.例例3 3 如下图表示某区域的交通网络，各条旁边所注的数字表示如下图表示某区域的交通网络，各条旁边所注的数字表示通过该公路所估计行驶的时间（单位：小时）。试问通过该公路所估计行驶的时间（单位：小时）。试问S S到到T T估计估计至少要行驶多少小时？并写出最短路径。至少要行驶多少小时？并写出最短路径。解：狄克斯特拉（解：狄克斯特拉（DijkstraDijkstra）算法列表如下：）算法列表如下：第16页，本讲稿共22页 迭代次数迭代次数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 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第17页，本讲稿共22页 最短路模型还可以应用于中心选址问题。所谓中心选址问题最短路模型还可以应用于中心选址问题。所谓中心选址问题就是在一个网络中选择一点，建立公用服务设施，为该网络就是在一个网络中选择一点，建立公用服务设施，为该网络中的客户提供服务，使得服务效率最高。比如一个区域的消中的客户提供服务，使得服务效率最高。比如一个区域的消防站、自来水厂、学校、变电站、银行商店等选址。为了提防站、自来水厂、学校、变电站、银行商店等选址。为了提高服务效率，自然的想法是将高服务效率，自然的想法是将 这些设施建立在中心地点。对这些设施建立在中心地点。对于规则的网络，例如圆形、矩形等，中心地点是显而易见的，于规则的网络，例如圆形、矩形等，中心地点是显而易见的，然而对于更多的网络是不规则的。应此，我们引入两个定义。然而对于更多的网络是不规则的。应此，我们引入两个定义。第18页，本讲稿共22页 例例4 4 教育部们打算在某新建城区建一所学校教育部们打算在某新建城区建一所学校,让附近七个居民区的让附近七个居民区的学生就近入学。七个居民区之间的道路如下图所示学生就近入学。七个居民区之间的道路如下图所示.学校应建在哪个居民区，学校应建在哪个居民区，才能使大家都方便？才能使大家都方便？（图中距离单位：百米）（图中距离单位：百米）解：由狄克斯特拉（解：由狄克斯特拉（DijkstraDijkstra）算法计算得各居民之间的最短距离列表如下算法计算得各居民之间的最短距离列表如下:ABCDEFG d(vd(vi i)di,jA034578101037B3032457724C4305568831D52502355(min)22(min)E7452013722(min)F8563102825G107853201035第19页，本讲稿共22页 从上表来看，应选择从上表来看，应选择D D作为学校的地址，这样最远的居民作为学校的地址，这样最远的居民区离学校的距离也只有区离学校的距离也只有500500米米.在现实生活中，同一网络中的各点要求提供的服务的数量也在现实生活中，同一网络中的各点要求提供的服务的数量也不尽不尽 相同。我们将各点要求提供的服务数量作为该点的权相同。我们将各点要求提供的服务数量作为该点的权数，重新考虑选址问题。数，重新考虑选址问题。例例5 5 在例在例4 4中，若七个区的学生人数分别为中，若七个区的学生人数分别为4040、2525、4545、3030、2020、3535、5050人，试问教育部门应将学校建在哪个居民区，人，试问教育部门应将学校建在哪个居民区，才能使大家都方便？才能使大家都方便？第20页，本讲稿共22页 所以应选择所以应选择E E作为新建学校的地址。作为新建学校的地址。ABCDEFGA0751801501402805001325B12001356080175350920C1607501501002104001095D20050225040105250870E28010022560035150850（min）F32012527090200100925G400175360150607001215第21页，本讲稿共22页 练习题练习题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第22页，本讲稿共22页