A new improvement for a K shortest paths algorithm
A new improvement for a K shortest paths algorithm
复制标题
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
E. Martins;Marta M. B. Pascoal;J. L. Santos
中科院分区：
文献类型：
--
作者：
E. Martins;Marta M. B. Pascoal;J. L. Santos
K条最短路问题是一个著名的网络优化问题，它的目的是对网络中的起始点和终点之间的K条最短路进行排序。解决这个问题的第一个算法是由1950年提出的，此后又提出了几个其他的算法。这些算法可以分为两类，一类是基于最优性原理的，另一类是基于确定最短路树的。最短路径此外，在这些类的第一，可以考虑标记算法和删除路径算法。本文提出了一个已知的删除路径算法的改进，当考虑最坏情况分析时，该算法的执行时间复杂度得到了改善。认为
The K shortest paths problem is a well known network optimization problem where it is intended to rank the K shortest paths between an initial and a terminal node in a network The rst algorithm for solving this problem appeared by the fties and since then several other algorithms have been proposed These algorithms can be divided into two classes one based on the Optimality Principle and another based on the determination of a tree of shortest paths Moreover in the rst of these classes there can be considered labeling algorithms and deletion path algorithms In this paper an improvement for a known deletion path algorithm is presented which results in the improvement of its execution time complexity when the worst case analysis is considered Comparative computational experiments are also reported allowing possible conclusions about the obtained performances when the average case is considered