dijkstra最短路径算法的一种高效率实现-

《dijkstra最短路径算法的一种高效率实现-》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Dijkstra最短路径算法的一种高效率实现*摘要在已存在的一些最短路径算法测试总结的基础上，根据GIS中网络计算的实际情况，从网络结构的拓扑表示以及Dijkstra算法中快速搜索技术的实现入手，提出了一种Dijkstra最短路径算法的高效率实现方法。关键词最短路径算法；网络分析；地理信息系统分类号P208；022AnEfficientImplementationofShortestPathAlgorithmBasedonDijkstraAlgorithmYueYangGongJianya(Na

2、tionalLaboratoryforInformationEngineeringinSurveying,MappingandRemoteSensing,WTUSM,12LuoyuRoad,Wuhan,China.30079)AbstractWiththedevelopmentofgeographicinformationscienceandthewideuseofGISsoftware,moreandmoreneedsarerequiredtothenetworkanalyses・Asthek

3、eyofnetworkanalyses,computingtheshortestpathsoveranetworkisanimportantproblemthatscholarsfacuson.StartwiththedatastructureduringitscomputationprocessandcombinedwithZhansevaluationofasetof1shortestpathalgorithms,thispaperpresentsanefficientmethodofrea

4、lizetheshortestpathalgorithmwhichisbasedonDijkstraalgorithm.Resultshowsthatthismethodperformswellinpractice・Keywordsshortestpathalgorithm；networkanalysis；GIS随着计算机的普及以及地理信息科学的发展，GIS因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布

5、局设计中发挥了重要的作用，而网络分析中最基本最关键的问题是最短路径问题。最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用、线路容量等。相应地，最短路径问题就成为最快路径问题、最低费用问题等。由于最短路径问题在实际中常用于汽车导航系统以及各种应急系统等，这些系统一般要求计算出到出事地点的最佳路线的时间应该在1S〜S内，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效率的。其实，无论是距离最短、时间最快还是费用最低，它们的核心算法都

6、是最短路径算法。经典的最短路径算法Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础,只是不同系统对Dijkstra算法采用了不同的实现方法。据统计，目前提出的此类最短路径的算法大约有17种。Zhan等人对其中的15种进行了测试，结果显示有3种效果比较好，它们分别是：TQQ、DKA(theDijkstra9salgorithmimplementedwithapproximatebuckets)以及DKD(theDijkstrasalgorithmimplementedwithdou

7、blebuckets),这些算法的具体内容可以参见文献［1］。其中TQQ算法的基础是图增长理论，较适合于计算单源点到其他所有点间的最短距离;后两种算法则是基于Dijkstra的算法,更适合于计两点间的最短路径问题［1］。总体来说，这些算法采用的数据结构及其实现方法由于受到当时计算机硬件发展水平的限制，将空间存储问题放到了一个很重要的位置，以牺牲适当的时间效率来换取空间节省。目前，空间存储问题已不是要考虑的主要问题，因此有必要对已有的算法重新进行考虑并进行改进，可以用空间换时间来提高最短路径算法的

8、效1经典Dijkstra算法的主要思想Dijkstra算法的基本思路是：假设每个点都有一对标号(dj,pj),其中dj是从起源点s到点j的最短路径的长度(从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：1)初始化。起源点设置为：①ds=0,ps为空;②所有其他点:di=oo5pi=?;③标记起源点s,记k=s，其他所有点设为未标记的。2）检验从所有已标记的点k到其直接连接的未标记的点j的距离