Abstract
Theshortest path problem is considered from a computational point of view. Eight algorithms which solve theshortest path tree problem on directed graphs are presented, together with the results of wide-ranging experimentation designed to compare their relative performances on different graph topologies. The focus of this paper is on the implementation of the different data structures used in the algorithms. A "Pidgin Pascal" description of the algorithms is given, containing enough details to allow for almost direct implementation in any programming language. In addition, Fortran codes of the algorithms and of the graph generators used in the experimentation are provided on the diskette.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A.V. Aho, J.E. Hopcroft and J.D. Ullman,The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, Mass., 1974).
M.S. Bazaraa and R.W. Langley, A dual shortest path algorithm, SIAM J. Appl. Math. 26, 3(1974)496.
R. Bellman, On a routing problem, Quart. Appl. Math. 16(1958)88.
G.B. Dantzig, All shortest routes in a graph, Theory of Graphs, Int. Symp., Rome 1966(Dunod, Paris, 1967) pp. 91–92.
E.V. Denardo and B.L. Fox, Shortest-route methods. I: Reaching, pruning, and buckets, Oper. Res. 27, 1(1979)161.
R.B. Dial, Algorithm 360: Shortest path forest with topological ordering, Commun. A.C.M. 12, 11(1969)632.
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, 3(1979)215.
E.W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1(1959)269.
J. Edmonds and R.M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, J. A.C.M. 10, 2(1972)248.
M. Florian, S. Nguyen and S. Pallottino, A dual simplex algorithm for finding all shortest paths, Networks 11 (1981)367.
R.W. Floyd, Algorithm 97: Shortest path, Commun. A.C.M. 5(1962)345.
L.R. Ford, Jr., Network flow theory, Rand Corporation Report No. P-293 (1956).
G. Gallo, Reoptimization procedures in shortest path problems, Rivista di Matematica e di Scienze Economiche e Sociali 3, 1(1980)3.
G. Gallo, Updating shortest paths in large-scale networks, paper presented at the Int. Workshop on Advances in Linear Optimization Algorithms and Software, Pisa, Italy (1980).
G. Gallo and S. Pallottino, A new algorithm to find the shortest paths between all pairs of nodes, Discr. Appl. Math. 4(1982)23.
G. Gallo and S. Pallottino, Shortest path methods: A unifying approach, Mathematical Programming Study 26(1986)38.
G. Gallo, S. Pallottino, C. Ruggeri and G. Storchi, Metodi ed algoritmi per la determinazione di cammini minimi, Monografie di Software Matematico, N.29 (1984).
J. Gilsinn and C. Witzgall, A performance comparison of labeling algorithms for calculating shortest path trees, Natl. Bureau of Standards, Technical Note N.772 (1973).
F. Glover, R. Glover and D. Klingman, Computational study of an improved shortest path algorithm, Networks 14(1984)25.
F. Glover, D. Klingman and N. Phillips, A new polynomially bounded shortest path algorithm, Oper. Res. 33(1985)65.
E. Horowitz and S. Sahni,Fundamentals of Data Structures (Pitman, London, 1976).
T.C. Hu, Revised matrix algorithms for shortest paths, SIAM J. Appl. Math. 15(1967)207.
D.B. Johnson, Algorithms for shortest paths, Ph.D. Dissertation, Cornell University, Report No. tr-73-169 (1973).
D.B. Johnson, A note on Dijkstra's shortest path algorithm, J. A.C.M. 20, 3(1973)385.
D.B. Johnson, Efficient algorithms for shortest paths in sparse networks, J. A.C.M. 24 1(1977)1.
E.L. Johnson, On shortest paths and sorting, Proc. 25th A.C.M. Annual Conference (1972) pp. 510–517.
A. Kershenbaum, A note on finding shortest path trees, Networks 11(1981)399.
D.E. Knuth,The Art of Computer Programming, Vol. 1:Fundamental Algorithms (Addison-Wesley, Reading, Mass., 1968).
D.E. Knuth,The Art of Computer Programming, Vol. 3:Sorting and Searching (Addison-Wesley, Reading, Mass., 1973).
E.L. Lawler,Combinatorial Optimization: Networks and Matroids (Holt, Rinehart and Winston, New York, 1976).
E.L. Lawler, Shortest path and network flow algorithms, Ann. Discr. Maths. 4(1979)251.
E.F. Moore, The shortest path through a maze, Proc. Int. Symp. on Theory of Switching, part 2, Harvard University Press (1959) pp. 285–292.
G.L. Nemhauser, A generalized permanent label setting algorithm for the shortest path between specified nodes, J. Math. Analysis and Appl. 38(1972)328.
S. Pallottino, Adaptation de l'algorithme de d'Esopo-Pape pour la determination de tous les chemins les plus courts: ameliorations et simplifications, CRT, University of Montreal, Publ. No. 136 (1979).
S. Pallottino, Shortest path methods: Complexity, interrelations and new propositions, Networks 14(1984)257.
U. Pape, Implementation and efficiency of Moore algorithms for the shortest route problem, Math. Progr. 7(1974)212.
U. Pape, Algorithm 562: Shortest path lengths, A.C.M. Transactions on Mathematical Software 6(1980)450.
U. Pape, Remark on algorithm 562, A.C.M. Transactions on Mathematical Software 9, 2(1983)260.
D.R. Shier and C. Witzgall. Properties of labeling methods for determining shortest path trees, J. Res. Natl. Bureau of Standards 86, 3(1981)317.
B. Simeone, Private communication, Bologna, Italy (1980).
Y. Tabourier, All shortest distances in a graph. An improvement to Dantzig's inductive algorithm, Discr. Math. 4(1973)83.
R.E. Tarjan, Complexity of combinatorial algorithms, SIAM Review 20, 3(1978)457.
R.E. Tarjan, Data structures and network algorithms, CBMS-NSF 44 (SIAM, Philadelphia, 1983).
D. Van Vliet, Improved shortest path algorithms for transport networks, Trans. Res. 12, 1(1978)7.
S. Warshall, A theorem on Boolean matrices, J. A.C.M. 9(1962)11.
J.W.J. Williams, Algorithm 232: Heapsort, Commun. A.C.M. 7(1964)347.
Author information
Authors and Affiliations
Additional information
Research carried out as part of the SOFMAT (Mathematical Software) activities of the Italian National Research Council (C.N.R.) "Progetto Finalizzato Informatica".
Rights and permissions
About this article
Cite this article
Gallo, G., Pallottino, S. Shortest path algorithms. Ann Oper Res 13, 1–79 (1988). https://doi.org/10.1007/BF02288320
Issue Date:
DOI: https://doi.org/10.1007/BF02288320