Management Science · 1971 · 2.6K citations · 6 references
ComputingComputer EngineeringComputer ScienceAlgorithmsComputer NetworksInterconnection NetworksAlgorithm AnalysisComputational ComplexityGraph AlgorithmsRoutingRouting AlgorithmsShortest Path AlgorithmsK-shortest PathsShortest Path LengthShortest Path ProblemsShortest PathsUpper Bound Computation
The paper proposes an algorithm for finding the K shortest loopless paths between two nodes in a network. The authors review existing K‑shortest loopless path algorithms and then introduce a new algorithm with theoretical justification. The new algorithm’s computational upper bound grows only linearly with K, making it far more efficient than prior methods, as confirmed by comparative experiments.
This paper presents an algorithm for finding the K loopless paths that have the shortest lengths from one node to another node in a network. The significance of the new algorithm is that its computational upper bound increases only linearly with the value of K. Consequently, in general, the new algorithm is extremely efficient as compared with the algorithms proposed by Bock, Kantner, and Haynes [2], Pollack [7], [8], Clarke, Krikorian, and Rausan [3], Sakarovitch [9] and others. This paper first reviews the algorithms presently available for finding the K shortest loopless paths in terms of the computational effort and memory addresses they require. This is followed by the presentation of the new algorithm and its justification. Finally, the efficiency of the new algorithm is examined and compared with that of other algorithms.
6
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
An Appraisal of Some Shortest-Path Algorithms
Stuart E. Dreyfus · Operations Research · 1969 · 997 citations