一种Dijkstra优化算法的研究与实现

Research and implementation of an optimized Dijkstra algorithm

最短路径计算是地理信息系统应用中的重要功能之一,经典的最短路径算法是D ijkstra算法,但该算法由于结构过于复杂导致计算效率较低,无法满足实际应用需求。从实际应用需求出发,针对D ijkstra算法的不足,在拓扑存储结构、拓扑关系数据结构以及拓扑网中节点存储顺序三方面对算法进行优化,通过分析与实际应用表明提出的D ijkstra改进算法不仅结构简单易于实现,而且算法效率高,能够满足实际应用需求。

Shortest path computation is one of the most important function in GIS application.Dijkstra algorithm is the classical one,but because of its complex structure,the algorithm is too low efficient to satify the pratical requirement.Considering the practical requirement and the deficiencies of the algorigthm,this paper optimized the algorithm from the topological storage structure,topological relation structure and order of the nodes.Through the analysis and practical use,it shows the optimized algorithm is not only easy to implement the structure,but also high efficient to satisfy the practical requirement.