Dijkstra 最短路径算法
摘 要 在已存在的一些最短路径算法测试总结的基础上,根据GIS中网络计算的实际情况,从网络结构的拓扑表示以及Dijkstra算法中快速搜索技术的实现入手,提出了一种Dijkstra最短路径算法的高效率实现方法。
关键词 最短路径算法;网络分析;地理信息系统
分类号 P208;O22
An Efficient Implementation of Shortest Path Algorithm
Based on Dijkstra Algorithm
Yue Yang Gong Jianya
(National Laboratory for Information Engineering in Surveying, Mapping and Remote
Sensing,
WTUSM, 129 Luoyu Road, Wuhan, China, 430079)
Abstract With the development of geographic information science and the wide use of GIS software, more and more needs are required to the network analyses. As the key of network analyses, computing the shortest paths over a network is an important problem that scholars facus on. Start with the data structure during its computation process and combined with F.Benjamin Zhans evaluation of a set of 15 shortest path algorithms, this paper presents an efficient method of realize the shortest path algorithm which is based on Dijkstra algorithm. Result shows that this method performs well in practice.
Key words shortest path algorithm; network analysis; GIS
随着计算机的普及以及地理信息科学的发展,GIS因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一,在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用,而网络分析中最基本最关键的问题是最短路径问题。最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其他的度量,如时间、费用、线路容量等。相应地,最短路径问题就成为最快路径问题、最低费用问题等。由于最短路径问题在实际中常用于汽车导航系统以及各种应急系统等(如110报警、119火警以及医疗救护系统),这些系统一般要求计算出到出事地点的最佳路线的时间应该在1 s~3 s内,在行车过程中还需要实时计算出车辆前方的行驶路线,这就决定了最短路径问题的实现应该是高效率的。其实,无论是距离最短、时间最快还是费用最低,它们的核心算法都是最短路径算法。经典的最短路径算法
——Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础,只是不同系统对Dijkstra算法采用了不同的实现方法。
据统计,目前提出的此类最短路径的算法大约有17种。F.Benjamin Zhan等人对其中的15种进行了测试,结果显示有3种效果比较好,它们分别是:TQQ(graph growth with two queues)、DKA (the Dijkstra's algorithm implemented with approximate buckets) 以及 DKD (the Dijkstras algorithm
implemented with double buckets ),这些算法的具体内容可以参见文献[1]。其中TQQ算法的基础是图增长理论,较适合于计算单源点到其他所有点间的最短距离;后两种算法则是基于Dijkstra的算法,更适合于计算两点间的最短路径问题[1]。总体来说,这些算法采用的数据结构及其实现方法由于受到当时计算
所以我们认为这种采用自定义结构的数组表示邻接表的方法是 Dijkstra 最短路径算法中比较好 的一种实现方法。 下表是本文讨论的 Dijkstra 最短路径算法的三种实现...
网络最 短路径算法的改进及实现 [ J]. 厦门大学学报 (自然科学版 ), 2005 ( 44): 40- 42 , [ 3] 乐阳等. D ijkstra最短路径算法的一种高效率实现....
举例说明了该算法的实现方法以及该算法的缺点: 即需要 网络结点 数平方级的 内存; 同时详细说明了一种基于 Dijkstra 算法的优化算法 邻接 结点算 法, 该 算法充...
D ijks tra算法的一种高效 率实现 [ J] . 计算机 与数字工 程, 2007, 7... Dijkstra 最短路径算法的... 6页 2下载券 最短路径dijkstra的精简... 3...
您的论文得到两院院士关注 文章编号 :1008-0570(2007)11-3-0275-03 软件时空 Dijkstra 最短路径算法的优化及其实现TheoptimizationandImplementationoftheShortestPath...
网络最短路径算法的改进及实现 ;〕 厦门大学学报 自然科学版) ,77/, ..) .7 5 ., 〔 ! (,(:〔-〕乐阳等! "#$%&’() 最短路径算法的一种高效率...
武汉,430074) 摘要:本文通过对 Dijkstra 最短路径搜索算法的分析,从数据存储结构方面对此问题进行了 探讨,并提出了一种数据文件结构,实验证明该实现具有较高的效率...
( n ×m ) 、四 快速 Dijkstra 最短路径优化算法 的实现 本算法的思想是通过减少查找具有最小 D ( v i ) 的顶点的时间 ,从而达到提高算法时间效率的目的 ...
您的论文得到两院院士关注 文章编号 :1008-0570(2007)11-3-0275-03 软件时空 Dijkstra 最短路径算法的优化及其实现TheoptimizationandImplementationoftheShortestPath...
热门文档