article · 1998
The k Shortest Paths Problem
Ernesto de Queirós Vieira Martins, Marta Margarida Braz Pascoal, José Luis Esteves dos Santos
Cited by 0Abstract and details only
Abstract
The shortest path problem is a classical network programming 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 we are concerned with the unconstrained ranking shortest paths problem. In the first part the problem is viewed as a generalization of the classical shortest path problem; conditions for finiteness and for the optimality principle being satisfied are studied as well as labeling shortest path algorithms are generalized. In the second part \n...
Cite this paper
Martins, E. D. Q. V., Pascoal, M. M. B., & dos Santos, J. L. E. (1998). The k Shortest Paths Problem.
Martins, Ernesto de Queirós Vieira, et al. “The k Shortest Paths Problem.” 1998.
Martins, Ernesto de Queirós Vieira, Marta Margarida Braz Pascoal, and José Luis Esteves dos Santos. 1998. “The k Shortest Paths Problem.”
Martins, E.D.Q.V., Pascoal, M.M.B. and dos Santos, J.L.E. (1998) ‘The k Shortest Paths Problem’.
@article{martins1998shortest,
title = {{The k Shortest Paths Problem}},
author = {Martins, Ernesto de Queirós Vieira and Pascoal, Marta Margarida Braz and dos Santos, José Luis Esteves},
year = {1998}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.