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

Research and implementation of an optimized Dijkstra algorithm

作　　者：蔡俊[1] 李钦富[1] 王金泉[1] 

机构地区：[1]中国电子科学研究院,北京100041

出　　处：《信息技术》2011年第4期104-107,共4页Information Technology

摘　　要：最短路径计算是地理信息系统应用中的重要功能之一,经典的最短路径算法是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.

关 键 词：最短路径 地理信息系统 DIJKSTRA算法 拓扑存储结构 优化 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]