×

A computational study of efficient shortest path algorithms. (English) Zbl 0659.90087

Five efficient shortest path algorithms are implemented and compared in this report. The selected algorithms are the most efficient, measured either in terms of worst case bounds or from previous computational studies. The algorithms include two using threshold functions, two using heaps, and one using buckets for sorting node labels. The last three algorithms have not been studied in detail before. The computational experiment employs a rigorous design to ensure that the results have statistical validity. Three different cost functions are generated to measure the sensitivity of each algorithm to cost distributions. Curve fittings are performed to summarize the results and they show high degrees of goodness-of-fit. The results reveal some heretofore unknown properties of some of the algorithms.

MSC:

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

Software:

Algorithm 360
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Lawler, E. L., Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart & Winston: Holt, Rinehart & Winston New York · Zbl 0358.68059
[2] Tarjan, R. E., Data Structures and Network Algorithms (1983), SIAM: SIAM Philadelphia, Pa · Zbl 0584.68077
[3] Dreyfus, S. E., An appraisal of some shortest-path algorithms, Opns Res., 17, 395-412 (1969) · Zbl 0172.44202
[4] Pallottino, S., Shortest-path methods: complexity, inter-relations and new propositions, Networks, 14, 257-267 (1984) · Zbl 0583.90103
[5] Gilsinn, J.; Witzgall, C., A performance comparison of labeling algorithms for calculating shortest path trees, (Nat. Bur. Stand. Tech. Note 772 (1973), U.S. Dept. of Commerce)
[6] Golden, B., Shortest path algorithms: a comparison, Opns Res., 24, 1164-1168 (1976) · Zbl 0343.90050
[7] Denardo, E.; Fox, B., Shortest-route methods. 1. Reaching, pruning, and buckets, Opns Res., 27, 161-186 (1979) · Zbl 0391.90089
[8] Dial, R.; Glover, F.; Karney, D.; Klingman, D., A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees, Networks, 9, 215-248 (1979) · Zbl 0414.68035
[9] Glover, F.; Glover, R.; Klingman, D., Computational study of an improved shortest path algorithm, Networks, 14, 25-36 (1984)
[10] Glover, F.; Klingman, D. D.; Phillips, N. V.; Schneider, R. F., New polynomial shortest path algorithms and their computational attributes, Mgmt Sci., 31, 1106-1128 (1985) · Zbl 0609.90103
[11] Dijkstra, E. W., A note on two problems in connexion with graphs, Num. Math., 1, 269-271 (1959) · Zbl 0092.16002
[12] Knuth, D. E., (The Art of Computer Programming, Vol. 3 (1973), Addison-Wesley: Addison-Wesley Reading, Mass) · Zbl 0302.68010
[13] M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms. IEEE Found. Comput. Sci.; M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms. IEEE Found. Comput. Sci.
[14] Dial, R., Algorithm 360 shortest path forest with topological ordering, Communs Ass. Comput. Mach., 12, 632-633 (1969)
[15] Glover, F.; Klingman, D.; Phillips, N., A new polynomially bounded shortest path algorithm, Opns Res., 33, 65-73 (1985) · Zbl 0578.90089
[16] Law, A. M.; Kelton, W. D., Simulation Modeling and Analysis (1982), McGraw-Hill: McGraw-Hill New York · Zbl 0489.65007
[17] Derigs, U., A shortest augmenting path method for solving minimal perfect matching problems, Networks, 11, 379-390 (1981) · Zbl 0475.05069
[18] Edmonds, J.; Karp, R., Theoretical improvements in algorithmic efficiency for network flow problems, J. Ass. Comput. Mach., 19, 248-264 (1972) · Zbl 0318.90024
[19] Gallo, G.; Pallottino, S.; Ruggen, C.; Starchi, G., Shortest paths: a bibliography, SOFTMAT Document 81-P1-4-SOFTMAT-27 (1982), Rome
[20] Hung, M. S.; Rom, W. O.; Waren, A. D., The Prüfer code for bipartite graphs, (Working paper (1984), College of Business Admin., Cleveland State Univ: College of Business Admin., Cleveland State Univ Cleveland, Ohio)
[21] Murphy, C. M.; Hung, M. S., Network generation using the Prüfer code, Comput. Opns Res., 13, 693-705 (1986) · Zbl 0617.90024
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.