Abstract
Four new shortest-path algorithms, two sequential and two parallel, for the source-to-sink shortest-path problem are presented and empirically compared with five algorithms previously discussed in the literature. The new algorithm, S22, combines the highly effective data structure of the S2 algorithm of Dial et al., with the idea of simultaneously building shortest-path trees from both source and sink nodes, and was found to be the fastest sequential shortest-path algorithm. The new parallel algorithm, PS22, is based on S22 and is the best of the parallel algorithms. We also present results for three new S22-type shortest-path heuristics. These heuristics find very good (often optimal) paths much faster than the best shortest-path algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
C. Berge and A. Ghouila-Houri,Programming, Games, and Transportation Networks, John Wiley and Sons, Inc., New York, NY, 1962.
D. Bertsekas and R. Gallager,Data Networks, Prentice-Hall, Englewood Cliffs, NJ, 1987.
G. Dantzig, “On the shortest route through a network,”Mgmt. Sci. 6 (1960) 187–190.
N. Deo and C. Pang, “Shortest-path algorithms: Taxonomy and annotation,”Networks 14 (1984) 275–323.
M. Desrochers, “A note on the partitioning shortest path algorithm,”Oper. Res. Letters 6 (1987) 183–187.
R. Dial, “Algorithm 360: Shortest path forest with topological ordering,”Commun. ACM,12 (1969) 632–633.
R. Dial, F. Glover, D. Karney, and D. Klingman,A Computational Analysis of Alternative Algorithms and Labeling Techniques for Finding Shortest Path Trees, CCS Report 291, Center for Cybernetic Studies, The University of Texas, Austin, TX 1977.
R. 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–250.
E. Dijkstra, “A note on two problems in connexion with graphs,”Numerische Mathematik 1 (1959) 269–271.
J. Divoky, “Improvements for the Thresh X2 shortest path algorithm,”Oper. Res. Letters 6 (1987) 227–232.
S. Dreyfus, “An appraisal of some shortest-path algorithms,”Oper. Res. 17 (1969) 395–412.
S. Even,Graph Algorithms, Computer Science Press, Rockville, MD, 1979.
G. Gallo, and S. Pallottino, “Shortest path methods: A unifying approach,”Math. Programming Study 26 (1986) 38–64.
G. Gallo, and S. Pallottino, “Shortest path algorithms,”Ann. Oper. Res. 13 (1988) 3–79.
F. Glover, R. Glover, and D. Klingman, “Computational study of an improved shortest path algorithm,”Networks 14 (1984) 25–36.
F. Glover, D. Klingman, N. Phillips, and R. Schneider, “New Polynomial Shortest Path Algorithms and Their Computational Attributes,”Mgmt. Sci. 31 (1985) 1106–1128.
P. Hart, N. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,”IEEE Trans. of Systems Science and Cybernetics,SSC-4 (1968) 100–107.
T. Hu,Combinatorial Algorithms, Addison-Wesley, Reading, MA, (1982).
P. Jensen and J. Barnes,Network Flow Programming, John Wiley and Sons, Inc., New York, NY, 1980.
D. Klingman, J. Mote, and D. Whitman,Improving Flow Management and Control Via Improving Shortest Path Analysis, CCS Report 322, Center for Cybernetic Studies, The University of Texas, Austin, TX, 1978.
E. Lawler,Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, New York, NY, 1987.
T. Mohr and C. Pasche, “A parallel shortest path algorithm,”Computing 40 (1988) 281–292.
T. Nicholson, “Finding the Shortest Route Between Two Points in a Network,”The Computer J. 9 (1966) 275–280.
C. Papadimitriou, and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs, NJ, 1987.
I. Pohl,Bi-directional and Heuristic Search in Path Problems, SLAC Report No. 104, Stanford, CA, 1969.
I. Pohl, “Bi-directional Search,”Machine Intelligence, B. Meltzer and D. Michie, eds.,6 (1971) 127–140.
M. Quinn,Designing Efficient Algorithms for Parallel Computers, McGraw-Hill, New York, NY, 1984.
R. Rockafellar,Network flows and monotropic optimization, John Wiley and Sons, Inc., New York, NY, 1984.
R. Tarjan,Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Helgason, R.V., Kennington, J.L. & Stewart, B.D. The one-to-one shortest-path problem: An empirical analysis with the two-tree Dijkstra algorithm. Comput Optim Applic 2, 47–75 (1993). https://doi.org/10.1007/BF01299142
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01299142