基于回溯法的Dijkstra算法改进及仿真  

Improvement and Simulation of Dijkstra Algorithm Based on Backtracking Algorithm

作　　者：王防修[1] 周康[1] 

机构地区：[1]武汉工业学院数学与计算机学院,湖北武汉430023

出　　处：《计算机仿真》2013年第11期352-355,共4页Computer Simulation

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

摘　　要：针对求有权图中任意两个顶点间的所有最短路径问题,提出了Dijkstra算法的改进。改进算法以加权图的邻接矩阵为基础,首先求出从一个顶点到其它各顶点的最短路径长度向量,然后由邻接矩阵和最短路径长度向量构造标识矩阵,最后用回溯法搜索标识矩阵得到从始点到其它各顶点的所有最短路径。改进算法具有使用范围广、计算规模小、计算过程简化、计算机易于实现等优点。改进算法的核心是用回溯法求解所有最短路径的运算,提出了从终点到始点的回溯求解问题,并且给出了求解任意两个顶点间的所有最短路径的快速算法。改进算法充分利用了标识矩阵所提供的路径信息经过回溯搜索得到两个顶点间的所有最短路径。仿真结果表明,改进算法对于求图中任意两个顶点间的所有最短路径行之有效。In view of all of the shortest path problem, this paper put forward an improveed Dijkstra algorithm based on the weighted graph adjacency matrix. First of all, the shortest path length vector was obtained from a vertex to all other vertices. Then it structsed an identity matrix by adjacency matrix and shortest path length vector. Finally, it used the backtracking algorithm and the identity matrix to search out all shortest paths obtained from the starting point to all other vertices. This algorithm has the advantages of wide using range, small scale of calculation, simpli- fied calculation process, and easy realizaion with a computer. The core of the algorithm is to use backtracking to solve all the shortest path computation. The paer put forward a backtracking method to solve the problem from the end to the starting point, discussed and gave a fast algorithm for any two vertices to find all the shortest path. The algorithm makes full use of the path information obtained from the identity matrix to search all shortest paths between the two vertices by backtracking. The simulation results show that it is very effective to find all of the shortest paths between any two vertices.

关 键 词：最短路径 狄杰斯特拉算法 标识矩阵 回溯法 所有最短路径 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]