×

zbMATH — the first resource for mathematics

Shortest paths algorithms: Theory and experimental evaluation. (English) Zbl 0853.90111
Summary: We conduct an extensive computational study of shortest paths algorithms, including some very recent algorithms. We also suggest new algorithms motivated by the experimental results and prove interesting theoretical results suggested by the experimental data. Our computational study is based on several natural problem classes which identify strengths and weaknesses of various algorithms. These problem classes and algorithm implementations form an environment for testing the performance of shortest paths algorithms. The interaction between the experimental evaluation of algorithm behavior and the theoretical analysis of algorithm performance plays an important role in our research.

MSC:
90C35 Programming involving graphs or networks
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] R.K. Ahuja, K. Mehlhorn, J.B. Orlin and R.E. Tarjan, ”Faster algorithms for the shortest path problem”,J. Assoc. Comput. Mach. 37 (2) (1990) 213–223. · Zbl 0696.68046 · doi:10.1145/77600.77615
[2] R.E. Bellman, ”On a routing problem”,Quart. Appl. Math. 16 (1958) 87–90. · Zbl 0081.14403
[3] P. van Emde Boas, R. Kaas and E. Zijlstra, ”Design and implementation of an efficient priority queue”,Math. Syst. Theory 10 (1977) 99–127. · Zbl 0363.60104 · doi:10.1088/0305-4470/10/1/020
[4] T.H. Cormen, C.E. Leiserson and R.L. Rivest,Introduction to Algorithms (MIT Press, Cambridge, MA, 1990). · Zbl 1158.68538
[5] E.V. Denardo and B.L. Fox, ”Shortest-route methods: 1. Reaching, pruning, and buckets”,Operations Research 27 (1979) 161–186. · Zbl 0391.90089 · doi:10.1287/opre.27.1.161
[6] R.B. Dial, ”Algorithm 360: Shortest path forest with topological ordering”,Comm. ACM 12 (1969) 632–633. · doi:10.1145/363269.363610
[7] R.B. Dial, F. Glover, D. Karney and D. Klingman, ”A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees”,Networks 9 (1979) 215–248. · Zbl 0414.68035 · doi:10.1002/net.3230090304
[8] E.W. Dijkstra, ”A note on two problems in connection with graphs”,Numer. Math. 1 (1959) 269–271. · Zbl 0092.16002 · doi:10.1007/BF01386390
[9] R.E. Erickson, C.L. Monma and A.F. Veinott Jr., ”Send-and-split method for minimum-concave-cost network flows”,Math. of Oper. Res. 12 (1979) 634–664. · Zbl 0667.90036 · doi:10.1287/moor.12.4.634
[10] L.R. Ford Jr., and D.R. Fulkerson,Flows in Networks (Princeton Univ. Press, Princeton, NJ, 1962) · Zbl 0106.34802
[11] M.L. Fredman and R.E. Tarjan, ”Fibonacci heaps and their uses in improved network optimization algorithms”,J. Assoc. Comput. Mach. 34 (1987) 596–615. · doi:10.1145/28869.28874
[12] M.L. Fredman and D.E. Willard, ”Trans-dichotomous algorithms for minimum spanning trees and shortest paths”,J. Comp. and Syst. Sci. 48 (1994) 533–551. · Zbl 0806.68057 · doi:10.1016/S0022-0000(05)80064-9
[13] H.N. Gabow and R.E. Tarjan, ”Faster scaling algorithms for network problems”,SIAM J. Comput. (1989) 1013–1036. · Zbl 0679.68079
[14] G. Gallo and S. Pallottino, ”Shortest paths algorithms”,Annals of Oper. Res. 13 (1988) 3–79.
[15] F. Glover, R. Glover and D. Klingman, ”Computational study of an improved shortest path algorithm”,Networks 14 (1984) 25–37. · Zbl 0605.90099 · doi:10.1002/net.3230140103
[16] F. Glover, D. Klingman and N. Phillips, ”A new polynomially bounded shortest paths algorithm”,Oper. Res. 33 (1985) 65–73. · Zbl 0578.90089 · doi:10.1287/opre.33.1.65
[17] A.V. Goldberg, ”Scaling algorithms for the shortest paths problem”, in:Proceedings 4th ACM-SIAM Symposium on Discrete Algorithms (1993) 222–231. · Zbl 0801.68132
[18] A.V. Goldberg and T. Radzik, ”A heuristic improvement of the Bellman-Ford algorithm”,Applied Math. Let. 6 (1993) 3–6. · Zbl 0771.68091 · doi:10.1016/0893-9659(93)90022-F
[19] M.S. Hung and J.J. Divoky, ”A computational study of efficient shortest path algorithms”,Comput. Oper. Res. 15 (1988) 567–576. · Zbl 0659.90087 · doi:10.1016/0305-0548(88)90052-4
[20] D.S. Johnson and C.C. McGeoch, eds.,Network Flows and Matching: First DIMACS Implementation Challenge (AMS, 1993). · Zbl 0781.00013
[21] A. Kershenbaum, ”A note on finding shortest paths trees”,Networks 11 (1981) 399. · doi:10.1002/net.3230110410
[22] E.L. Lawler,Combinatorial Optimization: Networks and Matroids (Holt Reinhart, and Winston, New York 1976). · Zbl 0413.90040
[23] B.Ju. Levit and B.N. Livshits,Neleneinye Setevye Transportnye Zadachi (Transport, Moscow, 1972), in Russian.
[24] J-F. Mondou, T.G. Crainic and S. Nguyen, ”Shortest path algorithms: A computational study with the C programming language”,Comput. Oper. Res. 18 (1991) 767–786. · Zbl 0741.90084 · doi:10.1016/0305-0548(91)90014-I
[25] E.F. Moore, ”The shortest path through a maze”, in:Proceedings of the Int. Symp. on the Theory of Switching (Harvard University Press, 1959) 285–292.
[26] S. Pallottino, ”Shortest-path methods: Complexity, interrelations and new propositions”,Networks 14 (1984) 257–267. · Zbl 0583.90103 · doi:10.1002/net.3230140206
[27] U. Pape, ”Implementation and efficiency of Moore algorithms for the shortest root problem”,Math. Prog. 7 (1974) 212–222. · Zbl 0288.90080 · doi:10.1007/BF01585517
[28] D. Shier and C. Witzgall, ”Properties of labeling methods for determining shortest paths trees”,J. Res. Natl. Bur. Stand. 86 (1981) 317–330. · Zbl 0463.68061 · doi:10.6028/jres.086.013
[29] R.E. Tarjan,Data Structures and Network Algorithms (Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983). · Zbl 0584.68077
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.