资源描述：
《最短路径算法在铁路客运系统中应用的研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第22卷第2期燕山大学学报Vol122No121998年4月JournalofYanshanUniversityApr11998最短路径算法在铁路客运系统中应用的研究ResearchontheApplicationoftheShortestPathAlgorithminthePassengerRailwayTransportsystem蔡淑兰摘要指出了在铁路客运系统中直接引用Dijkstra的1预备知识最短路径算法所造成的内存资源浪费问题,并提出了一套简便易行的解决方案1111有关定义和记号关键词最短路径,客运系统1定义1(图)一个图G是一个有序二元组〈V,AbstractInth
2、ispaper,theproblemofresourcewastere2E〉,记作G=〈V,E〉,其中,V是一个有限集,V中的sultingfromquotingtheshortestpathalgorithmdirectly元素称为G的结点,E是V中元素的无序偶的多重fromDijkstraispointedout,and,ahandyandeasysolvable集,这里每一个序偶称为G的一条边,记作ei=(Vi1,methodisproposed1Vi2),或等价地记作(Vi1,Vi2)1Keywordsshortestpath,passengertransportsyste
3、m1定义2(网)边带权的图称为网10引言图211是一个表示路程的交通网1在铁路客运系统中,最繁忙的工作之一就是回答旅客的乘车咨询1八十年代中期以前,这项工作都是由人工来完成1八十年代末到现在,随着技术的发展,计算机的应用范围不断地扩大,铁路运输系统中也正在逐步地引入计算机1目前,我国规模较大的火车站正在试用一些回答旅客乘车咨询的计算机软件1这些软件能够代替人来回答旅客有关乘车时间、乘车车次等简单问题1但对于象“如何用最短时间到达某地?”、“如何花最少的钱到达某地?”等问题,这些软件处理起来就非常困难,有的甚至没法回答1究其根本原因是没有处理好如何在微机上利用图1交通网示意图有限的内
4、存来寻找铁路交通网中有关的最短路径问Fig11Sketchoftrafficnet题1定义3(路径)在图G中,从结点V到结点1959年Dijkstra在文[1]中提出了一个在给定V’的路径是一个结点序列(V=Vi0,Vi1,⋯,的图中寻找最短路径的算法1该算法只考虑了时间Vim=V’),其中(Vij-1,Vij)∈E,1≤j≤m1特性而没有考虑空间特性1在实际应用时,如果图定义4(路径长度)是路径上边的数目或各中结点数目非常多,那么,直接引用该算法将会导边对应权的和1致大量的内存空间浪费和系统效率的降低1在图1中,长春到郑州共有两条路径,即(长本文将讨论如何在一个规模较大的图上(如
5、铁春,沈阳,天津,北京,郑州)、(长春,沈阳,天路交通网)应用Dijkstra算法来寻找最短路径1下面津,徐州,郑州)1其路径长度分别为:1841和先介绍一些预备知识11997年11月12日收到1蔡淑兰(CaiShulan),燕山大学计算机与信息工程系,秦皇岛066004(TheDepartmentofComputerandInformationEngi2neering,YanshanUniversity,Qinhuangdao066004)1158燕山大学学报1998年20321这样,长春到郑州的最短路径就是(长春,IFi=tTHENi:=vtxmlm+1沈阳,天津,北京,郑州)
6、1ElSEi:=i+1];112最短路径算法及其分析S:=S+[j];11211最短路径算法FORi:=1TOvtxnumDO1959年,Dijkstra在文[1]中提出了一个求给IFNOT(iINs)AND定图(或网)中一点s(称为源点)到另一点t(称(dist+da1costi>dist[i])为目标结点)间最短路径的算法1其基本思想是:THEN[dist[i]:=dist+da1costi];设已知图(或网)中最接近于结点s的m个结点及path[i]:=path+[i]{修改dist[i],从结点s到这些结点中每一个结点的最短路径(从si∈V-S}到其本身的最短路径长度为零)
7、1对结点s和这m]个结点着色1然后,最接近于s的第m+1个结点可ENDP;{shortpath-DIJ}按如下方法求得:11212算法分析对于每一个未着色的结点y,考虑所有已着色定理211算法shortpath-DIJ的时间复杂性为结点x,把边(x,y)接在从s到x的最短路径后O(n2),n为网中结点的总数1面,这样就得到从s到y的m条不同路径1从这m证明:第一个FOR循环的时间是O(n),第条路径中选出最短的路径,它就是从s到y的最短二个FOR循环共进行n-1次,每
