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

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.