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

摘要：

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

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

所属期刊栏目：30

分类号：TP391(计算技术、计算机技术)

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

在线出版日期：2013-12-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：352-355