Skip to main content
SpringerLink
Log in

Shortest path algorithms

  • Chapter I Shortest Paths
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A.V. Aho, J.E. Hopcroft and J.D. Ullman,The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, Mass., 1974).

    Google Scholar 

  2. M.S. Bazaraa and R.W. Langley, A dual shortest path algorithm, SIAM J. Appl. Math. 26, 3(1974)496.

    Google Scholar 

  3. R. Bellman, On a routing problem, Quart. Appl. Math. 16(1958)88.

    Google Scholar 

  4. G.B. Dantzig, All shortest routes in a graph, Theory of Graphs, Int. Symp., Rome 1966(Dunod, Paris, 1967) pp. 91–92.

    Google Scholar 

  5. E.V. Denardo and B.L. Fox, Shortest-route methods. I: Reaching, pruning, and buckets, Oper. Res. 27, 1(1979)161.

    Google Scholar 

  6. R.B. Dial, Algorithm 360: Shortest path forest with topological ordering, Commun. A.C.M. 12, 11(1969)632.

    Google Scholar 

  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, 3(1979)215.

    Google Scholar 

  8. E.W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1(1959)269.

    Google Scholar 

  9. J. Edmonds and R.M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, J. A.C.M. 10, 2(1972)248.

    Google Scholar 

  10. M. Florian, S. Nguyen and S. Pallottino, A dual simplex algorithm for finding all shortest paths, Networks 11 (1981)367.

    Google Scholar 

  11. R.W. Floyd, Algorithm 97: Shortest path, Commun. A.C.M. 5(1962)345.

    Google Scholar 

  12. L.R. Ford, Jr., Network flow theory, Rand Corporation Report No. P-293 (1956).

  13. G. Gallo, Reoptimization procedures in shortest path problems, Rivista di Matematica e di Scienze Economiche e Sociali 3, 1(1980)3.

    Google Scholar 

  14. 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).

  15. G. Gallo and S. Pallottino, A new algorithm to find the shortest paths between all pairs of nodes, Discr. Appl. Math. 4(1982)23.

    Google Scholar 

  16. G. Gallo and S. Pallottino, Shortest path methods: A unifying approach, Mathematical Programming Study 26(1986)38.

    Google Scholar 

  17. 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).

  18. 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).

  19. F. Glover, R. Glover and D. Klingman, Computational study of an improved shortest path algorithm, Networks 14(1984)25.

    Google Scholar 

  20. F. Glover, D. Klingman and N. Phillips, A new polynomially bounded shortest path algorithm, Oper. Res. 33(1985)65.

    Google Scholar 

  21. E. Horowitz and S. Sahni,Fundamentals of Data Structures (Pitman, London, 1976).

    Google Scholar 

  22. T.C. Hu, Revised matrix algorithms for shortest paths, SIAM J. Appl. Math. 15(1967)207.

    Google Scholar 

  23. D.B. Johnson, Algorithms for shortest paths, Ph.D. Dissertation, Cornell University, Report No. tr-73-169 (1973).

  24. D.B. Johnson, A note on Dijkstra's shortest path algorithm, J. A.C.M. 20, 3(1973)385.

    Google Scholar 

  25. D.B. Johnson, Efficient algorithms for shortest paths in sparse networks, J. A.C.M. 24 1(1977)1.

    Google Scholar 

  26. E.L. Johnson, On shortest paths and sorting, Proc. 25th A.C.M. Annual Conference (1972) pp. 510–517.

  27. A. Kershenbaum, A note on finding shortest path trees, Networks 11(1981)399.

    Google Scholar 

  28. D.E. Knuth,The Art of Computer Programming, Vol. 1:Fundamental Algorithms (Addison-Wesley, Reading, Mass., 1968).

    Google Scholar 

  29. D.E. Knuth,The Art of Computer Programming, Vol. 3:Sorting and Searching (Addison-Wesley, Reading, Mass., 1973).

    Google Scholar 

  30. E.L. Lawler,Combinatorial Optimization: Networks and Matroids (Holt, Rinehart and Winston, New York, 1976).

    Google Scholar 

  31. E.L. Lawler, Shortest path and network flow algorithms, Ann. Discr. Maths. 4(1979)251.

    Google Scholar 

  32. 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.

  33. G.L. Nemhauser, A generalized permanent label setting algorithm for the shortest path between specified nodes, J. Math. Analysis and Appl. 38(1972)328.

    Google Scholar 

  34. 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).

  35. S. Pallottino, Shortest path methods: Complexity, interrelations and new propositions, Networks 14(1984)257.

    Google Scholar 

  36. U. Pape, Implementation and efficiency of Moore algorithms for the shortest route problem, Math. Progr. 7(1974)212.

    Google Scholar 

  37. U. Pape, Algorithm 562: Shortest path lengths, A.C.M. Transactions on Mathematical Software 6(1980)450.

    Google Scholar 

  38. U. Pape, Remark on algorithm 562, A.C.M. Transactions on Mathematical Software 9, 2(1983)260.

    Google Scholar 

  39. 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.

    Google Scholar 

  40. B. Simeone, Private communication, Bologna, Italy (1980).

  41. Y. Tabourier, All shortest distances in a graph. An improvement to Dantzig's inductive algorithm, Discr. Math. 4(1973)83.

    Google Scholar 

  42. R.E. Tarjan, Complexity of combinatorial algorithms, SIAM Review 20, 3(1978)457.

    Google Scholar 

  43. R.E. Tarjan, Data structures and network algorithms, CBMS-NSF 44 (SIAM, Philadelphia, 1983).

    Google Scholar 

  44. D. Van Vliet, Improved shortest path algorithms for transport networks, Trans. Res. 12, 1(1978)7.

    Google Scholar 

  45. S. Warshall, A theorem on Boolean matrices, J. A.C.M. 9(1962)11.

    Google Scholar 

  46. J.W.J. Williams, Algorithm 232: Heapsort, Commun. A.C.M. 7(1964)347.

    Google Scholar 

Download references

Author information

Author notes

  1. Stefano Pallottino

    Present address: Department of Informatics, University of Pisa, I-56100, Pisa, Italy

Authors and Affiliations

  1. Department of Informatics, University of Pisa, 40, Corso Italia, I-56100, Pisa, Italy

    Giorgio Gallo

  2. I.A.C., National Research Council, 137, viale del Policlinico, I-00161, Roma, Italy

    Stefano Pallottino

Authors
  1. Giorgio Gallo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Stefano Pallottino
    View author publications

    You can also search for this author in PubMed Google Scholar

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

Reprints 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

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02288320

Keywords

Search

Navigation