图论论文迪杰斯特拉(Dijkstra)-弗罗伊德(Floyd)算法

摘要：主要介绍最短路的两种算法，迪杰斯特拉(Dijkstra)以及算法在实际问题中的应用。关键字：图论，最短路径，树，生成树，迪杰斯特拉(Dijkstra)，弗罗伊德(Floyd)算法1引言最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。2最短路定义①1若图G=G(V,E)中各边e都赋有一个实数W(e),称为边e的权,则称这种图为赋权图,记为G=G(V,E,W)。定义②2若图G=G(V,E)是赋权图且0We,eEG,若u是iv到jv的路Wu的权,则称Wu为u的长,长最小的iv到jv的路Wu称为最短路。3、Dijkstra算法基本步骤③：令：_23,1,,,,insvisvvv并令：10,jjWvTvvs1、对jvs，求min,jiijjTvWvwTv。2、求minjjvsTv得kTv，使kTv=minjjvsTv令kkWvTv3、若knvv则已找到1v到nv的最短路距离kWv，否则令ik从s中删去iv转1这样经过有限次迭代则可以求出1v到nv的最短路线，可以用一个流程图来表示：第一步先取10Wv意即1v到1v的距离为0,而jTv是对jTv所赋的初值。第二步利用1Wv已知,根据min,jiijTvWvw对jTv进行修正。第三步对所有修正后的jTv求出其最小者kTv。其对应的点kv是1v所能一步到达的点jv中最近的一个,由于所有0Wu。因此任何从其它点jv中转而到达kv的通路上的距离都大于1v直接到kv的距离kTv,因此kTv就是1v到kv的最短距离,所以在算法中令kkWvTv并从s中删去kv,若k=n则knWvWv就是1v到nv的最短路线,计算结束。否则令ikvv回到第二步,继续运算,直到k=n为止。这样每一次迭代,得到1v到一点kv的最短距离,重复上述过程直到knvv。3最短路的应用3.1在运输网络中的应用④设6个城市126,,,vvv之间的一个公路网(图1)每条公路为图中的边,边上的权数表示该段公路的长度(单位:百公里),设你处在城市1v,那么从1v到6v应选择哪一路径使你的费用最省。解:首先设每百公里所用费用相同,求1v到6v的费用最少,既求1v到6v的最短路线。为了方便计算,先作出该网络的距离矩阵,如下:1234561234560525015921081058025910202520vvvvvvvvLvvvv(0)设1234560,,,,,,jWvTvvsvvvvv,(1)第一次迭代①计算,2,3,4,5,6jTvj如下22112min,min,055TvTvWvw33113min,min,022TvTvWvw44114min,min,0TvTvWvw56,TvTv②取32minjjvsTvTv,令332WvTv③由于36kn,令2456,,,,3svvvvi转(1)第二次迭代:①算,2,4,5,6jTvj如下22323min,min5,213TvTvWvw44334min,min8,288TvTvWvw55335min,min10,21010TvTvWvw66336min,min,2TvTvWvw②取2min3jjvsTvTv令223WvTv③由于26kn,令456,,2svvvi转(1)第三次迭代:①算,4,5,6jTvj如下44224min,min8,358TvTvWvw55225min,min10,3910TvTvWvw6Tv②取444min8,8jjvsTvTvWvTv③由于46kn,令56,4svvi转(1)第四次迭代:①算,5,6jTvj如下55445min,min10,2810TvTvWvw66446min,min,8513TvTvWvw②取555min10,10jjvsTvTvWvTv③由于56kn,令6sv转(1)第五次迭代:①算,6jTvj如下66556min,min13,10212TvTvWvw②由于6kn。因此已找到1v到6v的最短距离为12。计算结束。找最短路线:逆向追踪得132456vvvvvv最短距离为12,即从城市1v到城市6v的距离最短,即费用最省。3.3其他应用最短路径问题在交通网络结构的分析，交通运输线路(公路、铁路、河流航运线、航空线、管道运输线路等)的选择，通讯线路的建造与维护，运输货流的最小成本分析，城公共交通网络的规划等，都有直接应用的价值。最短路径问题在实际中还常用于汽车导航系统以及各种应急系统等(如110报警、119火警以及120医疗救护系统)这些系统一般要求计算出到出事地点的最佳路线的时间应该在15一35内，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效率的。在很多目标信息引导系统的设计中．需要获得最优化路径引导信息。例如，在日益增多的高层建筑、大型公共建筑(超级市场、博物馆、医院、游乐场等)场台的火灾事故现场救生疏导系统，需要根据现场情况动态地为逃生者实时提供最短的安全通道指引信息；而当这些场合发生盗窃、抢劫等突发犯罪事件时，安全监控系统如能为警方实时提供通向罪犯所处位置最短搜索路径信息．则可以达到迅速制止犯罪的目的。在设计一个大型高层建筑火灾事故现场救生疏导系统时，将图论中Dijkstra算法应用于目标信息引导系统的设计中，通过Dijkstra算法，首先计算出任一指定位置点距各疏导出口的最短路径树，进而通过编制辅助方向指示箭头程序．动态地将火灾事故现场救生疏导路径引导图加以显示，从而达到优化目标引导路径的目的．按照城乡运输一体化的总体思路，为实现农村村村通客车的目标，针对农村客运线路繁杂，节点众多的特点，布局优化农村公路客运网的规划和建设是农村发展的重要内容，为落实贯彻中央2004年l号文件，解决三农问题，全面建设小康社会，实现人便于行，货畅其流。需要从规划布局的角度，科学地审视农村公路网和客运线路。村村通客车，是农村客运网的基本要求，但农村村屯点多面广，线路繁杂，网络节点众多，道路迂回曲折。如何科学合理的选择路径，即达到农村客运网络畅达便捷，合理布局即是关键问题。现有的客运线路，系依托路网，村屯自然经济和区域特点，经经营者申报，交通运政管理部门审批而形成；其路径是否合理，线路覆盖和便捷程度，总体资源配置是否优化，尚无完整定量分析，系统和路网是否科学等一系列问题还有待确定。4结语本文将最短路理论应用到实际生活中，尤其是在舰船通道路线中的应用具有很重要的意义。将实际生活中出现的安全隐患尽量降低。同时也凸显出学习和应用最短路问题原理的重要性。另外，最短路问题在城市道路建设、物资供应站选址等问题上也有很重要的作用。分析和研究最短路问题趋于热门化。注：①殷剑宏,吴开亚.图论及其算法M.中国科学技术出版社②秦裕瑗,秦明复.运筹学简明教材M.高等教育出版社