交通运输网络的二叉堆索引及路径算法优化

Index of Binary Heap for Transportation Network and Optimization of Shortest Path Algorithms

交通运输网络的最短路径分析是地理信息系统网络分析最常见的应用之一.该文在二叉堆索引结构的基础上改进了计算最短路径的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.