交通运输网络的最短路径分析是地理信息系统网络分析最常见的应用之一.该文在二叉堆索引结构的基础上改进了计算最短路径的Dijkstra算法和A*算法，采用了多种优化策略提高算法的运行效率.首先，应用二叉堆索引提高了交通运输网络存储结构的读取效率；其次，通过数据类型的低精度损耗简化和运算类型的简化，提高了算法的计算效率.另外，优化了A*算法中估计函数的计算方式，有效降低了搜索空间，提高了Dijkstra算法和A*算法的整体计算效率.实验结果表明Dijkstra算法的改进方法可使计算速度提高7倍以上，对A*算法的改进可使计算速度提高200倍以上.
Shortest path finding of transportation network is one of the commonest application scenes for geographic information system network analysis. This paper improves Dijkstra and A* algorithms based on binary heap index. It presents several optimal strategies to improve the efficiency of both algorithms. Firstly, it uses binary heap index to improve the access efficiency of storage structure in GIS networks. Then it simplifies the data types and operation types as keeping the precision of data calculation of algorithms. Additionally, it decreases searching space effectively by optimizing the estimation function of A* algorithm. Experimental results show that the improvement makes Dijkstra algorithm up to 7 times and A* algorithm up to 200 times faster than before.
[1] 张波良, 张瑞昌, 关佶红. 道路网上最短路径算法综述[J]. 计算机应用与软件, 2014, 10(2):1-9. Zhang B L, Zhang R C, Guang J H. A survey on shortest path algorithm in road networks[J]. Computer Applications and Software. 2014, 10(2):1-9. (in Chinese)
[2] Cherkassky B V, Goldberg A V, Radzik T. Shortest paths algorithms theory and experimental evaluation[J]. Mathematical Programming, 1996, 73:129-174.
[3] 王树西, 吴政学. 改进的Dijkstra最短路径算法及其应用研究[J]. 计算机科学, 2012, 5(1):223-228. Wang S X, Wu Z X. Improved Dijkstra shortest path algorithm and its application[J]. Computer Science, 2012, 5(1):223-228. (in Chinese)
[4] 段莉琼, 朱建军, 王庆社, 等. 改进的最短路径搜索A*算法的高效实现[J]. 海洋测绘, 2004, 9(1):20-22. Duan L Q, Zhu J J, Wang Q S, et al. Fast realization of the improved A* algorithm for shortest route[J]. Hydrographic Surveying and Charting, 2004, 9(1):20-22. (in Chinese)
[5] 陆锋. 最短路径算法:分类体系与研究进展[J]. 测绘学报, 2001, 8(1):269-275. Lu F. Shortest path algorithms taxonomy and advance in research[J]. Acta Geodaetica et Cartographica Sinica, 2001, 8(1):269-275. (in Chinese)
[6] 乐阳, 龚健雅. Dijkstra最短路径算法的一种高效率实现[J]. 武汉测绘科技大学学报, 1999, 24(3):209-211. Yue Y, Gong J Y. An efficient implementation of shortest path algorithm based on Dijikstra algorithm[J]. Journal of Wuhan Technical University of Surveying and Mapping, 1999, 24(3):209-211. (in Chinese)
[7] Domenico C, Simone F. Two-levels-greedy:a generalization of Dijkstra's shortest path algorithm[J]. Electronic Notes in Discrete Mathematics, 2004:81-86.
[8] Hassanzadeh R, Mahdavi-Amiri N. A genetic algorithm for solving fuzzy shortest path problems with mixed fuzzy arc lengths[J]. Mathematical and Computer Modeling, 2013, 57(1/2):84-99.
[9] 闫春望, 黄玮, 王劲松. 一种并行模糊神经网络最短路径算法[J]. 计算机应用研究, 2016, 11(1):3391-3395 Yan C W, Huang W, Wang J S. Parallel fuzzy neural network shortest plan algorithm[J]. Application Research of Computers, 2016, 11(1):3391-3395. (in Chinese)
[10] Kumar P, Kumar A. Linear programming approach for solving fuzzy critical path problems with fuzzy parameters[J]. Applied Soft Computing, 2014, 21:309-319.
[11] Klunder G A, Post H N. The shortest path problem on large-scale real-road networks[J]. Networks, 2006(4):182-194.
[12] 范林林, 李翔, 张晶. 基于不同交通工具多约束条件的最短路径算法研究[J]. 测绘工程, 2016, 12(1):32-37. Fan L L, Li X, Zhang J. Research on shortest path selection based on different transportation under multiple constraints[J]. Engineering of Surveying and Mapping, 2016, 12(1):32-37. (in Chinese)
[13] Jafee J M. Algorithms for finding paths with multiple constraints[J]. Networks, 1984, 14:95-116.
[14] Wagner D, Willhalm T, Zarliagis C. Geometric containers for efficient shortest-path computation[J]. ACM Journal of Experimental Algorithmics, 2005, 10(12):1-30.
[15] Lauther U. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background[J]. Geoinformation und Mobilität-von der Forschung zur Praktischen Anwendung, 2004, 22:219-230.
[16] Bazlamacci C F, Hindi K S. Minimum-weight spanning tree algorithms:a survey and empirical study[J]. Computers and Operations Research, 2001(8):767-785.
[17] 李晶, 闫军. 基于Dijkstra算法和Floyd算法的物流运输最短路径研究[J]. 科技信息, 2012, 34(1):575-576. Li J, Yan J. Shortest path finding in transportation based on Dijkstra and Floyd algorithm[J]. Science & Technology Information, 2012, 34(1):575-576. (in Chinese)
[18] 宫恩超, 李鲁群. 基于Bellman-Ford算法的动态最优路径算法设计[J]. 测绘通报, 2011, 8(1):26-28. Gong E C, Li L Q. The optimal path algorithm design based on Bellman-Ford algorithm[J]. Bulletin of Surveying and Mapping, 2011, 8(1):26-28. (in Chinese)
[19] 徐建闽, 王钰, 林培群. 大数据环境下的动态最短路径算法[J]. 华南理工大学学报(自然科学版), 2015, 10(1):1-7. Xu J M, Wang Y, Lin P Q. A dynamic shortest path algorithm for big data[J]. Journal of South China University of Technology (Natural Science Edition), 2015, 10(1):1-7. (in Chinese)
[20] Said B, Arindam D, Mohamed T, et al. Shortest path problem using Bellman algorithm under neutrosophic environment[J]. Complex & Intelligent Systems, 2019, 12:409-416.
[21] Festa P, Guerriero F, Napoletano A. An auction-based approach for the re-optimization shortest path tree problem[J]. Computational Optimization and Applications, 2019, 12:851-893.
[22] Daniele F, Paola F, Francesca G. An efficient exact approach for the constrained shortest path tour problem[J]. Optimization Methods & Software, 2019, 12:1-20.
