K最短路径算法综述

为了进一步推广应用K最短路径(K shortest paths,KSP)算法并为深入研究该类算法提供相关资料。根据路径限制条件,将KSP问题分为一般KSP问题和限定无环KSP问题,归纳总结了求解每类KSP问题的基本思路、研究现状和研究进展。KSP问题非常复杂,在实际应用中所需处理的数据规模非常庞大,使得算法效率成了评价KSP算法的一个重要指标。在分析各种KSP算法时尤其关注其时间复杂度,指出KSP问题未来的研究方向,将为满足多约束的最短路径等问题的研究提供有益的参考。

一种改进的求解前N条最短路径问题的多重标号算法

求前N条最短路径问题是一个在实际工程中有着广泛应用背景的重要问题.针对传统问题描述中存在的局限,对该问题的定义进行了扩展,从而使此问题的求解更为完备.介绍了求解传统N最短路径问题的多重标号算法的基本思想,分析了其存在的问题,提出了相应的针对扩展N最短路径问题的改进算法.在详细描述算法实现的基础上,对改进算法的时间和空间复杂度进行了理论分析,并分别与理论严密算法中的候选删除边算法和有损算法中的遗传算法进行了对比实验.结果表明,本文算法能以更好的时间性能正确地求解得到全局最优路径集.

基于标记边的城市轨道交通网络KSP算法

城市轨道交通网络票务清分和客流分配都需要以路径搜索作为基础。由于城市轨道交通网络拓扑结构图不适用标记点的路径搜索算法,如对其拓展将导致路径搜索时间延长。为此,基于标记边的思想,考虑进出站时间对路径选择的影响,提出适用于城市轨道交通网络的K最短路径(KSP)搜索算法,以实现无须拓展网络的KSP搜索。在北京城市轨道交通网络上的应用结果表明,与传统的标记点Yen算法相比,该算法计算效率显著提高,在搜索同一OD对之间的KSP时能够节省至少一半时间。

求解无环K短路径的Dijkstra算法

对多个标号的求解K短路径的Dijkstra改进算法进行完善,引入两个前驱节点矩阵pre和Kpre,通过这两个矩阵可以求出起始点到当前节点的当前路径,并判断这条路径是否有环,从而在寻找K短路的过程中避免了环的出现,完善后的算法可以求出前K短无环路径,该算法仅需要较少的额外计算量,所以仍然保持了算法的多项式复杂性.然后在不同规模的网络上对完善后的算法进行数值试验,验证了算法的正确性和有效性.