Dijkstra优化算法及其在电子导游中的应用  

Application of Optimized Dijkstra Algorithm in Electronic Guiding

作　　者：王涛春[1] 齐学梅[1] 赵诚[1] 

机构地区：[1]安徽师范大学数学计算机科学学院,安徽芜湖241003

出　　处：《安徽师范大学学报（自然科学版）》2010年第6期525-529,共5页Journal of Anhui Normal University(Natural Science)

基　　金：安徽省优秀青年科技基金(08040106806);安徽省自然科学基金(070412043);安徽师范大学青年科学基金(2007xqn58)

摘　　要：导游电子化是旅游产业的发展趋势,最短路径搜索是电子导游系统的关键技术之一.经典的Dijkstra算法须花费大量时间用于计算最短路径以外的结点,从而影响了算法的速度.在分析景区结点分布特点和移动设备特性的基础上,对Dijkstra算法进行了优化,优化算法基于对景区结点进行区域划分,缩小了考虑结点的范围,在搜索时仅对相关区域内的结点进行处理,从而提高了算法的速度,最后对优化算法进行了正确性证明和性能分析.Electronic guiding is the development trend of tourist industry.The shortest path searching is one of the key techniques applied in electronic guiding system.However,Dijkstra＇s algorithm takes a lot of time to search nodes away from the shortest path,which lowers the efficiency of such algorithm.Dijkstra＇s algorithm is optimized based on the analysis of features of scenic spots and mobile devices.The principle of such optimized algorithm is to divide nodes in scenic spots and decrease the number of nodes needed to be considered in searching,thus improve the efficiency of algorithm.Finally,validity of this optimized algorithm is proved and the performance analysis of it is presented.

关 键 词：DIJKSTRA 区域分块 最短路径 电子导游 

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