Deviation Algorithms for Ranking Shortest Paths
Deviation Algorithms for Ranking Shortest Paths
复制标题
DOI：
10.1142/s0129054199000186
复制
发表时间：
1999-09
期刊：
影响因子：
--
通讯作者：
E. Martins;Marta M. B. Pascoal;J. L. Santos
中科院分区：
文献类型：
--
作者：
E. Martins;Marta M. B. Pascoal;J. L. Santos
最短路径问题是一个经典的网络问题，已被广泛研究。不仅确定最短路径，而且列出K条最短路径（对于给定的整数K>1）的问题也是一个经典的问题，但没有被深入研究，尽管它具有明显的实际意义。通常考虑两种不同类型的问题：无约束和约束K最短路问题。在有约束K最短路问题中，所有的路都必须满足一定的条件，例如，必须是无环的。本文针对无约束问题提出了一种新的算法，即计算K条最短路的超集。它还表明，排名无环路径不持有一般的最优性原则，以及如何提出的算法的无约束问题可以适应排名无环路径。
The shortest path problem is a classical network problem that has been extensively studied. The problem of determining not only the shortest path, but also listing the K shortest paths (for a given integer K>1) is also a classical one but has not been studied so intensively, despite its obvious practical interest. Two different types of problems are usually considered: the unconstrained and the constrained K shortest paths problem. While in the former no restriction in considered in the definition of a path, in the constrained K shortest paths problem all the paths have to satisfy some condition – for example, to be loopless. In this paper new algorithms are proposed for the uncontrained problem, which compute a super set of the K shortest paths. It is also shown that ranking loopless paths does not hold in general the Optimality Principle and how the proposed algorithms for the unconstrained problem can be adapted for ranking loopless paths.