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

摘要

针对求有权图中任意两个顶点间的所有最短路径问题,提出了Dijkstra算法的改进.改进算法以加权图的邻接矩阵为基础,首先求出从一个顶点到其它各顶点的最短路径长度向量,然后由邻接矩阵和最短路径长度向量构造标识矩阵,最后用回溯法搜索标识矩阵得到从始点到其它各顶点的所有最短路径.改进算法具有使用范围广、计算规模小、计算过程简化、计算机易于实现等优点.改进算法的核心是用回溯法求解所有最短路径的运算,提出了从终点到始点的回溯求解问题,并且给出了求解任意两个顶点间的所有最短路径的快速算法.改进算法充分利用了标识矩阵所提供的路径信息经过回溯搜索得到两个顶点间的所有最短路径.仿真结果表明,改进算法对于求图中任意两个顶点间的所有最短路径行之有效.