| Autor: |
de Queirós Vieira Martins, Ernesto, Pascoal, Marta Margarida Braz, Santos, José Luis Esteves Dos, Olariu, S. |
| Předmět: |
|
| Zdroj: |
International Journal of Foundations of Computer Science; Sep1999, Vol. 10 Issue 3, p247, 15p |
| Abstrakt: |
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 is 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 unconstrained 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. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
