Implementation of algorithms for k shortest loopless paths. (English) Zbl 0642.90097

Perko, Aarni

Networks 16, No. 2, 149-160 (1986).

Implementations of loopless \(k\) shortest path algorithms are examined. Efficient storage structures for a large number of paths are given. A fast algorithm for determining the shortest paths in Yen’s method is developed. Timing experiments show that a hybrid of the methods of S. Clarke, A. Krikorian and J. Rausen [J. Soc. Ind. Appl. Math. 11, 1096-1102 (1964; Zbl 0217.29003)] and J. Y. Yen [Manage. Sci. 17, 712-716 (1971; Zbl 0218.90063)] is generally the fastest, although not significantly. Using upper bounds for the lengths of paths essentially improves all methods.

MSC:

90C35	Programming involving graphs or networks
65K05	Numerical mathematical programming methods

Keywords:

Implementations; loopless k shortest path algorithms; Efficient storage structures

Citations:

Zbl 0217.29003; Zbl 0218.90063

References:

[1]	Clarke, J. Soc. Indust. Appl. Mathematics 11 pp 1096– (1963)
[2]	Glover, Networks 14 pp 25– (1984)
[3]	Hoffman, J. Assoc. Comput. Mach. 6 pp 506– (1959) · Zbl 0100.13103 · doi:10.1145/320998.321004
[4]	Katoh, Networks 12 pp 411– (1982)
[5]	Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, New York (1976).
[6]	McCormack, Comm. Assoc. Comput. Mach. 24 pp 801– (1981)
[7]	Pape, ACM Trans. Math. Software 6 pp 450– (1980)
[8]	Perko, Information Processing Letters 16 pp 21– (1983)
[9]	Schrage, ACM Trans. Math. Software 5 pp 132– (1979)
[10]	Shier, Networks 9 pp 195– (1979)
[11]	Weigand, Computing 12 pp 273– (1974)
[12]	Weigand, Computing 16 pp 139– (1976)
[13]	Yen, Manag. Sci. 17 pp 712– (1971)