最短路问题及其应用

大连海事大学图论论文姓名：学号：专业：计算机科学与技术院系：信息科学技术2009级摘要：关键字:主要介绍最短路的两种算法，迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法。以及这两种关键字:图论，最短路径，树，生成树，迪杰斯特拉(Dijkstra)，弗罗伊德(Floyd)算法最短路问题及其应用1引言图论是应用数学的一个分支，它的概念和结果来源非常广泛，最早起源于一些数学游戏的难题研究，如欧拉所解决的哥尼斯堡七桥问题，以及在民间广泛流传的一些游戏难题，如迷宫问题、博弈问题、棋盘上马的行走路线问题等.这些古老的难题，当时吸引了很多学者的注意.在这些问题研究的基础上又继续提出了著名的四色猜想和汉米尔顿（环游世界）数学难题.1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域的问题时，发挥出越来越大的作用.在实践中，图论已成为解决自然科学、工程技术、社会科学、军事等领域中许多问题的有力工具之一。最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短，还可以引申到其它的度量，如时间、费用、线路容量等。最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点，很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。2最短路2.1最短路的定义对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图^w,,>0）的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的，该算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因

此由Ford提出了Ford算法，它能有效地解决含有负权的最短路问题。但在现实生活中，我们所遇到的问题大都不含负权，所以我们在(七>0)的情况下选择Dijkstra算法。定义①1若图G=G(V,E)中各边e都赋有一个实数W(e)，称为边e的权，则称这种图为赋权图，记为G=G(V,E,W)。定义②2若图G=G(V,E)是赋权图且W(e)>0,eeE(G),若u是匕到七的路W(u)的权,则称W(u)为u的长，长最小的％到匕的路W(u)称为最短路。若要找出从v到v的通路u，使全长最短，即minW(u)=ZW(e)。in2.2最短路问题算法的基本思想及基本步骤e沪2.2最短路问题算法的基本思想及基本步骤在求解网络图上节点间最短路径的方法中,目前国内外一致公认的较好算法有迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法。这两种算法中，网络被抽象为一个图论中定义的有向或无向图，并利用图的节点邻接矩阵记录点间的关联信息。在进行图的遍历以搜索最短路径时,以该矩阵为基础不断进行目标值的最小性判别,直到获得最后的优化路径。Dijkstra算法是图论中确定最短路的基本方法,也是其它算法的基础。为了求出赋权图中任意两结点之间的最短路径，通常采用两种方法。一种方法是每次以一个结点为源点,重复执行Dijkstra算法n次。另一种方法是由Floyd于1962年提出的Floyd算法，其时间复杂度为O妇)，虽然与重复执行Dijkstra算法n次的时间复杂度相同，但其形式上略为简单，且实际运算效果要好于前者。Dijkstra算法基本步骤③:令：s={v.},i=1,S={v2,v3,,v}W(v)=0并令*T(v)=；vesjj1、对ves，求minT(v),W(v)+w}=T(v)。jj.ijj2、求minTET(v)，使T(v)=minT(v)}jkkjvjesvjvjes令W(v)=T(v)kk3、若vk=v^则已找到V1到vn的最短路距离W(vj，否则令i=k从s中删去V,转1这样经过有限次迭代则可以求出七到Vn的最短路线，可以用一个流程图来表示:这样经过有限次迭代则可以求出七到Vn的最短路线，可以用一个流程图来表示:第一步先取W(vi)=0意即V］到V］的距离为0,而T(vj)是对T(vj)所赋的初值。第二步利用W(v)已知，根据minT(v),W(v)+w｝对T(v)进行修正。ijiijj第三步对所有修正后的T(v,)求出其最小者T(vk)。其对应的点vk是v］所能一步到达的点v,中最近的一个，由于所有W(u)>0。因此任何从其它点v,中转而到达vk的通路上的距离都大于v］直接到vk的距离T(vj,因此T(七)就是v］到vk的最短距离，所以在算法中令W(vk)=T“)并从s中删去vk,若k=n则W(v^)=W(Tn)就是七到v〃的最短路线,计算结束。否则令匕二V回到第二步，继续运算,直到卜n为止。这样每一次迭代,得到七到一点v的最短距离，重复上述过程直到丁v。ijFloyd算法的基本原理和实现方法为:如果一个矩阵D=_d」其中j0表示i与j间的距离,若i与J间无路可通，则』为无穷大。i与J间的最短距离存在经过i与J间的上和不经过ijk两种情况，所以可以令k=1,2,3,…,n,n（n为节点数）。检查"与门+匕的值,在此,门与"分别为目前所知的i到k与k到j的最短距离,因此,d^+dkj就是i到j经过k的最短距离。所以，若有d>d+d，就表示从i出发经k再到j的距离要比原来的i到j距离短,自然ijikkj把i到j的^重写成dk+d*每当一个k搜索完,d〃就是目前i到j的最短距离。重复这一过程，最后当查完所有k时,d就为i到j的最短距离。ijij3最短路的应用3.1在运输网络中的应用④设6个城市v,v,…,v之间的一个公路网（图1）每条公路为图中的边，边上的权数表示该126段公路的长度（单位:百公里）,设你处在城市V1，那么从V1到V6应选择哪一路径使你的费用最省。解:首先设每百公里所用费用相同,求v1到v6的费用最少，既求v1到v6的最短路线。为了方便计算,先作出该网络的距离矩阵,如下：[vv10v25v32v48v58v81v5015982L=v21081083v8580254v89102025v888520L6—1(0)设W(v)=0,T(v)=3,veS={v,v,v,v,v),1j23456(1)第一次迭代①计算T(v.),j=2,3,4,5,6如下T(v2)=minT(v),W(v)+w)=min{3,0+5)=5T(v3)=minT(v),W(v)+w)=min{3,0+2)=2T(v)=minT(v),W(v)+w)=min{3,0+3)=3T(v)=3,T(v)=3/②取minVjEST(v)}=2=T(v)令W(v)=T(v)=2

②取minVjES③由于k=3公(n=6)，令s={v,v,v,v},i=3转(1)2456第二次迭代：算T(v.),j=2,4,5,6如下T(vj=minT(v),W(v)+w}=min{5,2+1)=3T(vj=minT(v),W(v)+w}=min{8,2+8}=8T(v5)=minT(v),W(v)+w}=min{10,2+10)=10T(v6)=minT(v),W(v)+w)=min{3,2+3)=3取min{T(v))=3=T(v)令W(v)=T(v)=3j222—ves③由于k=2公(n=6),令s={v4,v5,v6)i=2转(1)第三次迭代：算T(v.),j=4,5,6如下T(vj=minT(v),W(v)+w)=min{8,3+5)=8T(v5)=minT(v),W(v)+w)=min{10,3+9)=10T(v)=36取min{T(v))=8=T(v),W(v)=T(v)=8j444—ves③由于k=4公(n=6)，令i={七,七}i=4转(1)第四次迭代：①算T(v^),j=5,6如下T(v5)=minT(v),W(v)+w}=min{10,2+8)=10T(v6)=min{T(v),W(v)+w}=min{“,8+5)=13②取min{T(v)}=10=T(v),W(v)=T(v)=10j555—③由于k=5公(n=6),令s={v}转(1)6第五次迭代：①算T(v.),j=6如下T(v6)=minT(v6),W(v5)+w56}=min{13,10+2)=12②由于k=6=n。因此已找到v1到v6的最短距离为12。计算结束。找最短路线:逆向追踪得vTvTvTvTvTv132456最短距离为12,即从城市v1到城市v6的距离最短,即费用最省。3.2在舰船通道路线设计中的应用⑤利用图论的经典理论和人群流量理论研究舰船人员通道路线的优化设计及最优线路选择。首先介绍图论相关理论，对船舶通道进行路网抽象，建立网络图，然后根据人群流动的相关理论，选取不同拥挤情况下的人员移动速度，从而确定各条路段（包括楼梯）的行程时间。以行程时间作为通道网络的路权，得出路阻矩阵以选择一对起点7终点的最短时间路线为目标，建立最短路径问题的数学模型，利用经典的Floyd算法确定最短路径。将此方法应用于某舰艇多层甲板的通道网络中,计算结果并进行讨论，最后在此研究的基础上对通道设计相关问题的深化和拓展进行了探讨和总结,并提出设想。路线优化技术通常采用图论中的“图”来表示路网，船舶通道路网与图论的路网对应关系为:结点通道的交叉口或断头路的终点；边两结点之间的路段称为边,若规定了路段的方向，则称为弧;边（弧）的权路段某个或某些特征属性的量化表示。路权的标定决定了最短的路径搜索依据，也就是搜索指标。根据不同的最优目标,可以选择不同的路段属性。由于舰船上除了平面上的通道之外还有垂直方向的楼梯（或直梯）,如果以最短路程距离作为优化目标,路线的效率未必最高（距离最短未必耗时最少）。所以，以最短行程时间作为优化的目标，道路权重即为各路段的平均行程时间。对于要研究的对象，取各条通道的起点（或终点）和交叉点为图的顶点，各路段为边，路权为路段行走的平均时间。寻找从起点到终点的最短时间路径即为最优路径。在规定了结点、边和权值以后，便将路网抽象为一个赋权无向图或赋权有向图，从而确定路网中某两地间的最优路线便转化为图论中的最短路径问题。首先将空间问题抽象为图，图2为某舰的两层甲板的部分抽象图，上下两个平面上纵横交错的直线为各层甲板的主要通道，连接两层甲板的直线表示楼梯，包括2个直梯和3个斜梯。每条路段上的标注（a，b）中,a表示路段实际长度或者楼梯的类型，m;b表示此路段的行程时间（即路权）,s如（40,32）。图2两层甲板的部分抽象图图3赋权图再利用上述求最短的方法即可求得需要的通道路线。3.3其他应用最短路径问题在交通网络结构的分析，交通运输线路（公路、铁路、河流航运线、航空线、管道运输线路等）的选择，通讯线路的建造与维护，运输货流的最小成本分析，城公共交通网络的规划等，都有直接应用的价值。最短路径问题在实际中还常用于汽车导航系统以及各种应急系统等（如110报警、119火警以及120医疗救护系统）这些系统一般要求计算出到出事地点的最佳路线的时间应该在15一35内，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效率的。在很多目标信息引导系统的设计中.需要获得最优化路径引导信息。例如，在日益增多的高层建筑、大型公共建筑（超级市场、博物馆、医院、游乐场等）场台的火灾事故现场救生疏导系统，需要根据现场情况动态地为逃生者实时提供最短的安全通道指引信息；而当这些场合发生盗窃、抢劫等突发犯罪事件时，安全监控系统如能为警方实时提供通向罪犯所处位置最短搜索路径信息.则可以达到迅速制止犯罪的目的。在设计一个大型高层建筑火灾事故现场救生疏导系统时，将图论中Dijkstra算法应用于目标信息引导系统的设计中，通过Dijkstra算法，首先计算出任一指定位置点距各疏导出口的最短路径树，进而通过编制辅助方向指示箭头程序.动态地将火灾事故现场救生疏导路径引导图加以显示，从而达到优化目标引导路径的目的.按照城乡运输一体化的总体思路，为实现农村村村通客车的目标，针对农村客运线路繁杂，节点众多的特点，布局优化农村公路客运网的规划和建设是农村发展的重要内容，为落实贯彻中央2004年l号文件，解决三农问题，全面建设小康社会，实现人便于行，货畅其流。需要从规划布局的角度，科学地审视农村公路网和客运线路。村村通客车，是农村客运网的基本要求，但农村村屯点多面广，线路繁杂，网络节点众多，道路迂回曲折。如何科学合理的选择路径，即达到农村客运网络畅达便捷，合理布局即是关键问题。现有的客运线路，系依托路网，村屯自然经济和区域特点，经经营者申报，交通运政管理部门审批而形成；其路径是否合理，线路覆盖和便捷程度，总体资源配置是否优化，尚无完整定量分析，系统和路网是否科学等一系列问题还有待确定。4结语本文将最短路理论应用到实际生活中，尤其是在舰船通道路线中的应用具有很重要的意义。将实际生活中出现的安全隐患尽量降低。同时也凸显出学习和应用最短路问题原理的重要性。另外，最短路问题在城市道路建设、物资供应站选址等问题上也有很重要的作用。分析和研究最短路问题趋于热门化。参考文献：【1】卜月华图论及其应用南京：东南大学出版社，2000【2】基于图论的舰船通道路线优化余为波王涛2008【3】最短路问题在运输网络中的应用李玲200