Finding the \(K\) shortest loopless paths in a network. (English) Zbl 0218.90063

Yen, J. Y.

Manage. Sci., Theory 17, 712-716 (1971).

Summary: 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 J. Bock, H. Kantner and J. Haynes [An algorithm (the \(r\)-th best path algorithm) for finding and ranking paths through a network, Research Report, Armour Research Foundation, Chicago, Illinois, November 15, 1957], M. Pollack [Oper. Res. 9, 578–580 (1961; Zbl 0096.35403), J. Math. Anal. Appl. 3, 547–559 (1961; Zbl 0112.12105)], S. Clarke, A. Krikorian and J. Rausen [J. Soc. Ind. Appl. Math. 11, 1096-1102 (1964; Zbl 0217.29003)], M. Sakarovitch [The \(k\) shortest routes and the \(k\) shortest chains in a graph, Operations Research, Center, University of California, Berkeley, Report ORC-32 (1966)] 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.

MSC:

90C35	Programming involving graphs or networks
05C85	Graph algorithms (graph-theoretic aspects)

Citations:

Zbl 0096.35403; Zbl 0112.12105; Zbl 0217.29003