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

Application of Optimized Dijkstra Algorithm in Electronic Guiding

导游电子化是旅游产业的发展趋势,最短路径搜索是电子导游系统的关键技术之一.经典的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.