-
题名有向非负权图中经过必经节点集最短路径算法
被引量:3
- 1
-
-
作者
杨志勇
叶冯彬
冯艳辉
刘秀秀
朱岩
-
机构
中国科学院大学
中国科学院国家空间科学中心
成都理工大学
-
出处
《电子设计工程》
2017年第16期32-36,41,共6页
-
文摘
传统的Dijkstra算法只是针对起点和终点求解最短路径,而不能解决从起点出发,经过必经节点集,到达终点的无重复节点且无回路的最短路径问题。为此,在有向非负权图中,提出了Dijkstra算法和回溯法相结合的方法。对Dijkstra算法改进,并求解关键节点(起点,终点和必经节点)间的最短路径,进而从关键节点所构成的矩阵中采用回溯法得到目标路径。通过实际的算法实现,测试大量的有向非负权图数据,证实了算法的有效性和正确性。
-
关键词
DIJKSTRA算法
回溯法
深度优先搜索
最短路径
必经节点集
有向非负权图
-
Keywords
Dijkstra algorithm
backtracking algorithm
depth-first search method
shortest path
anecessary set of nodes
directed and non-negative weighted graph
-
分类号
TP393
[自动化与计算机技术—计算机应用技术]
-