期刊论文

中文

计算机仿真

1006-9348

2013

30

11

352-355

10.3969/j.issn.1006-9348.2013.11.080

国家自然科学基金资助项目(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 pro...