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

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