Finding the <i>K</i> Shortest Loopless Paths in a Network

TLDR

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.

Abstract

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.