改进Dijkstra算法在GIS导航应用中最短路径搜索研究

研究GIS在电子导航系统应用中的最短路径搜索效率问题。在电子导航系统中对最短路径的搜索效率要求很高。随着城市发展交通线路剧增,传统的基于Dijkstra算法的GIS导航系统不能适应日益复杂的交通线路,存在最短路径搜索效率过低的问题。考虑到GIS空间分布的特性,提出了改进的Dijkstra算法用以解决GIS导航中的最短路径搜索问题。改进算法不仅避免了传统Dijkstra算法逐个节点遍历搜索,而且根据方向优先特性缩小搜索范围,大大减少了搜索工作量,并通过改变搜索节点存储的数据结构提高了最短路径的搜索效率。实验表明,这种改进算法较之传统算法能够有效提高最短路径的搜索效率,满足了电子导航系统对最短路径搜索效率的要求,取得了满意的结果。

Research on Shortest Path Search of Improved Dijkstra Algorithm in GIS Navigation Application

Research on the application of GIS navigation system is the shortest path search efficiency. hhe electronic navigation system has high demand for the shortest path search efficiency. With urban development, traffic lines increase, and the traditional Dijkstra algorithm based on GIS navigation system can not adapt to the increasingly complex traffic lines. The shortest path search efficiency is too low. Considering the GIS spatial distribution characteristics, this paper proposed the improvement Dijkstra algorithm to solve the shortest path search problem in GIS navigation. The improved algorithm not only avoids the case that traditional Dijkstra algorithm traverses the search by node, but also according to priority narrow search direction features range, greatly reduces the workload search, and through the change of the storage of data structure search node improves the shortest path search efficiency. Experiment indicates that compared with the traditional method the improved algorithm can effectively improve the shortest path algorithm of the search efficiency, and satisfy the shortest path search efficiency requirements of the electronic navigation system, and obtaines satisfactory results.