A enumeração dos K trajectos mais curtos
Authors
Abstract
The K Shortest Paths Problem can be considered as a generalization of the classical Shortest Path Problem, since it is intended to determine not only the shortest path between two nodes, but also the second shortest path, ..., until the K-th shortest path between that pair of nodes. When it is intended to determine only loopless paths (that is, paths with no cycles) we have the K Shortest Loopless Paths Problem.Although the first problem verifies the Optimality Principle, the second one does not and therefore the development of rather different algorithms for the resolution of both problems was necessary.
In this paper, after a brief analisys of these two problems, the notion of shortest paths tree is introduced. After a classification of some of the known algorithms for the K Shortest Paths Problem, and using the shortest paths tree concept, those two problems can be related in a manner which allows the development of new algorithms for its resolution. Finally, some of those algorithms are presented.