-
题名K最短路径算法综述
被引量：47
- 1
-
-
作者
徐涛
丁晓璐
李建伏
-
机构
中国民航大学计算机科学与技术学院
中国民航信息技术科研基地
-
出处
《计算机工程与设计》
CSCD
北大核心
2013年第11期3900-3906,3911,共8页
-
基金
天津市应用基础及前沿技术研究计划基金项目(09JCYBJC02300)
中央高校基本科研业务费用中国民航大学专项B类基金项目(ZXH2011B003)
-
文摘
为了进一步推广应用K最短路径(K shortest paths,KSP)算法并为深入研究该类算法提供相关资料。根据路径限制条件,将KSP问题分为一般KSP问题和限定无环KSP问题,归纳总结了求解每类KSP问题的基本思路、研究现状和研究进展。KSP问题非常复杂,在实际应用中所需处理的数据规模非常庞大,使得算法效率成了评价KSP算法的一个重要指标。在分析各种KSP算法时尤其关注其时间复杂度,指出KSP问题未来的研究方向,将为满足多约束的最短路径等问题的研究提供有益的参考。
-
关键词
KSP问题
路径限制条件
一般KSP问题
限定无环KSP问题
时间复杂度
-
Keywords
K shortest paths problem restriction conditiom general K shortest paths problem constrained loopless K shortest paths problem
time complexity
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名基于标记边的城市轨道交通网络KSP算法
被引量：2
- 2
-
-
作者
唐继孟
孙全欣
杜鹏
陈志杰
-
机构
北京交通大学城市交通复杂系统理论与技术教育部重点实验室
北京交通大学交通运输学院
-
出处
《计算机工程》
CAS
CSCD
北大核心
2019年第1期292-296,302,共6页
-
基金
国家自然科学基金重大项目(71390332)
国家自然科学基金青年基金(71001006)
-
文摘
城市轨道交通网络票务清分和客流分配都需要以路径搜索作为基础。由于城市轨道交通网络拓扑结构图不适用标记点的路径搜索算法,如对其拓展将导致路径搜索时间延长。为此,基于标记边的思想,考虑进出站时间对路径选择的影响,提出适用于城市轨道交通网络的K最短路径(KSP)搜索算法,以实现无须拓展网络的KSP搜索。在北京城市轨道交通网络上的应用结果表明,与传统的标记点Yen算法相比,该算法计算效率显著提高,在搜索同一OD对之间的KSP时能够节省至少一半时间。
-
关键词
城市轨道交通
K最短路径
标记边
路径搜索
无环路径
-
Keywords
urban rail transit
K Shortest paths(KSP)
labeling edge
path searching
loopless path
-
分类号
TP29
[自动化与计算机技术—检测技术与自动化装置]
-
-
题名求解无环K短路径的Dijkstra算法
被引量：2
- 3
-
-
作者
赵见
-
机构
中国矿业大学理学院
-
出处
《淮阴师范学院学报（自然科学版）》
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
[自动化与计算机技术—计算机软件与理论]
-
