On algorithms for finding the k shortest paths in a network
Author:
Abstract
This paper presents, within a unified framework, several new algorithms for computing k shortest paths in a network. These algorithms utilize strategies which have proved to be efficient in solving shortest path problems. In addition, a computational study was conducted to assess the effects of the different “arc processing” orders which are characteristic of each algorithm. Testing was performed using generated classes of moderately large grid, complete and random networks. Two particular algorithms emerge as the most promising among those evaluated.Keywords
This publication has 12 references indexed in Scilit:
- Iterative methods for determining the k shortest paths in a networkNetworks, 1976
- More on k th shortest pathsCommunications of the ACM, 1975
- Implementation and efficiency of Moore-algorithms for the shortest route problemMathematical Programming, 1974
- On computing sets of shortest paths in a graphCommunications of the ACM, 1974
- A Note on an Algebra for the k Best Routes in a NetworkIMA Journal of Applied Mathematics, 1973
- Finding the K Shortest Loopless Paths in a NetworkManagement Science, 1971
- Algorithm 360: shortest-path forest with topological ordering [H]Communications of the ACM, 1969
- An Appraisal of Some Shortest-Path AlgorithmsOperations Research, 1969
- Solutions of the kth best route through a network — A reviewJournal of Mathematical Analysis and Applications, 1961
- A note on two problems in connexion with graphsNumerische Mathematik, 1959