-
题名求解无环K短路径的Dijkstra算法
被引量：2
- 1
-
-
作者
赵见
-
机构
中国矿业大学理学院
-
出处
《淮阴师范学院学报（自然科学版）》
CAS
2012年第1期8-12,52,共6页
-
基金
国家自然科学基金资助项目(70901073)
中央高校基本科研业务费专项基金项目(2010LKSX01)
-
文摘
对多个标号的求解K短路径的Dijkstra改进算法进行完善,引入两个前驱节点矩阵pre和Kpre,通过这两个矩阵可以求出起始点到当前节点的当前路径,并判断这条路径是否有环,从而在寻找K短路的过程中避免了环的出现,完善后的算法可以求出前K短无环路径,该算法仅需要较少的额外计算量,所以仍然保持了算法的多项式复杂性.然后在不同规模的网络上对完善后的算法进行数值试验,验证了算法的正确性和有效性.
-
关键词
DIJKSTRA算法
K短路
无环
多标号
-
Keywords
dijkstm algorithm
K-shortest paths
loopless
many labels
-
分类号
TP319
[自动化与计算机技术—计算机软件与理论]
-
