基于改进Dijkstra算法的路径优化仿真研究  

Research on Route Optimization Simulation Based on An Improved Dijkstra Algorithm

作　　者：郝新刚[1] 任传祥[1] 刘法胜[1] 王英锐[1] 

机构地区：[1]山东科技大学信息与电气工程学院,青岛市266510

出　　处：《公路》2011年第7期177-180,共4页Highway

基　　金：国家自然科学基金资助项目(70671008);山东省研究生创新计划(SDYC08011);山东省"泰山学者"建设工程专项资助项目

摘　　要：在分析传统Dijkstra算法的基础上,针对该算法在路径优化中存在的不足,主要采用邻接表与循环链表相结合的方式存储数据,同时通过改进的快速排序算法对权值进行排序,实现了对邻接节点的快速搜索,得到了一种改进的Dijkstra算法。将其应用于最优路径的搜索,通过实例对该算法进行仿真分析,验证了算法的有效性。On the basis of analyzing tradition Dijkstra algorithm,in view of insufficiency this algorithm in the route optimization which exists,the way that combine the adjacency list and the circular linked list is mainly used to store date,sorting to the weight is simultaneously carried on through the improved fast sorting algorithm,fast search to the adjacent node is realized,and an improved Dijkstra algorithm is obtained.It is applied in the optimal path search,the simulation analysis are carried on through the example to this algorithm,the algorithm validity is confirmed.

关 键 词：DIJKSTRA算法 快速排序算法 路径优化 邻接表与循环链表 

分 类 号：U491.13[交通运输工程—交通运输规划与管理]