Dijkstra最短路径算法改进研究及应用.doc

Dijkstra最短路径算法改进研究及应用
赵雍
(陕西省交通规划设计研究院,陕西西安 710068)
摘要 Dijkstra算法是求解最短路径问题的经典算法。但是,在开发交通地理信息系统时,公路线形矢量图中,可能存在大量的折线段,以及大量的端点,如果直接利用此算法构造端点之间的邻接矩阵,要耗费大量宝贵的计算时间和存储空间,从而使其在实际应用中,对求解复杂路线图形的最短路径显得非常困难。针对在实际应用中存在的问题,本文提出了对传统的Dijkstra最短路径算法改进的新方法,即对复杂的公路网数据进行预处理,生成路网拓扑结构数据文件,并结合Dijkstra算法按路径长度递增次序产生最短路径的思想,来解决实际公路网复杂线状图形的最短路径问题。最后,利用VC++语言工具,将这种方法在1:20 万陕西省交通地理信息系统中进行实现,证明此方法是准确和高效的。
关键词地理信息系统;Dijkstra算法;最短路径;公路网;拓扑关系
Improvement Research on Dijkstra Shortest Path Algorithm and Its Application
Zhao Yong
(Shaanxi Provincial Transport Planning Design and Research Institute, Shaanxi Xi’an 710068)
Abstract:The Dijkstra algorithm is one of a classical algorithms which to solves the shortest path problem. However, in practice, when we design a special Geographic Information System for Transportation, there are possibly a large number of poly lines and vertexes in the road linear vector graphics. If we directly make use of this conventional algorithm, we must make the adjacent matrix between one vertex and the other. And it will consume puting time and storage space, so it is very difficult to be used in the practical project. Therefore, in allusion to the above questions, this paper puts forward an improved method. The contents are as follows: On the one hand, we need to preprocess plex and unreasonable work data, and then make a work topology data file. On the other hand, bine the