一种基于Dijkstra最短路径算法的改进算法  

A Kind of Shortest Path Algorithm Based on Dijkstra

作　　者：王智广[1] 王兴会[1] 李妍[1] 

机构地区：[1]中国石油大学(北京)信息学院,北京102249

出　　处：《内蒙古师范大学学报（自然科学汉文版）》2012年第2期195-200,共6页Journal of Inner Mongolia Normal University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(60803159)

摘　　要：Dijkstra算法是求解最短路径的经典算法,是在许多应用中解决最短路径问题的理论基础,但实际应用中涉及的许多限制条件要求人们必须对该算法进行改进和优化.在分析经典Dijkstra算法思想的基础上,给出Dijkstra算法的一种改进算法.在该算法中图的存储表示采用邻接表的方式,避免邻接矩阵在工程应用中的局限性.在最短路径的计算过程中,采用优先级队列与反向N叉树相结合的方式,以便通过实现可降级的优先队列来改进Dijkstra算法.给出了改进形Dijkstra算法的方法和流程,分析了其算法复杂度,并对改进后的算法进了详细的分析和测试.Shortest path algorithm has important practical value in engineering practice and Dijkstra algorithm is a classical algorithm for solving the shortest path.Dijkstra algorithm is the theoretical basis for many practical works to solve the shortest path problem,but many of the restrictions involved in the actual project,therefore,there must be the algorithm improvement and optimization.On the basis of analyzing the classical Dijkstra algorithm,the paper discusses an improved algorithm of Dijkstra algorithm.By using Map which is stored in the algorithm to the adjacency table,it can avoid the limitations of the adjacency matrix in the project;Moreover,in the calculation of the shortest path,using a combination of the priority queue with reverse N-tree.In order to down grade the priority queue to improve the Dijkstra algorithm.The paper puts forwards the methods and processes to improve the shape Dijkstra algorithm,and analyzes the complexity of the algorithm and do some detailed testing and results analysis.

关 键 词：DIJKSTRA算法 路网 邻接表 反向N叉树 最短路径 

分 类 号：TP319[自动化与计算机技术—计算机软件与理论]