Abstract
We analyze a simple method for finding shortest paths inEuclidean graphs (where vertices are points in a Euclidean space and edge weights are Euclidean distances between points). For many graph models, the average running time of the algorithm to find the shortest path between a specified pair of vertices in a graph withV vertices andE edges is shown to beO(V) as compared withO(E +V logV) required by the classical algorithm due to Dijkstra.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A. V. Aho, J. E. Hopcroft, and J. D. Ullman.The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA (1974).
E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs.Numerishe Mathematik, 1 (1959).
R. Durrett. Oriented Percolation in Two Dimensions.The Annals of Probability, 12, 4 (December 1984), 999–1040.
R. J. Elliott and M. E. Lesk. Route Finding in Street Maps by Computers and People.Proc. AAAI-82 Natl. Conference in Artificial Intelligence, Pittsburgh, PA (August 1982), 258–261.
M. L. Fredman and R. E. Tarjan. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.Proc. 25th Annual Symposium on Foundations of Computer Science, West Palm Beach, FL (October 1984), 338–346. The longer version of the paper will appear inJournal of the ACM.
H. N. Gabow, Z. Galil, and T. H. Spencer. Efficient Implementation of Graph Algorithms Using Contraction.Proc. 25th Annual Symposium on Foundations of Computer Science, West Palm Beach, FL (October 1984), 347–357.
B. L. Golden and M. Ball. Shortest Paths with Euclidean Distances: An Explanatory Model.Networks, 8 (1978), 297–314.
G. H. Gonnet. Expected Length of the Longest Probe Sequence in Hash Code Searching.Journal of the ACM, 28, 2 (April 1981), 289–304.
P. E. Hart, N. J. Nilsson, and B. Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths.IEEE Transactions on Systems Science and Cybernetics, 4, 2 (July 1968), 100–107.
E. L. Lawler, M. G. Luby, and B. Parker. Finding Shortest Paths in Very Large Networks.Proc. WG '83 Intl. Workshop on Graphtheoretic Concepts in Computer Science, Osnabrück, West Germany (June 1983), 184–199.
M. Loève.Probability Theory. Volume I. Graduate Texts in Mathematics, Springer-Verlag, New York (fourth edition 1977).
R. Sedgewick.Algorithms. Addison-Wesley, Reading, MA (1983).
R. E. Tarjan.Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA (1983).
J. S. Vitter. Faster Methods for Random Sampling.Communications of the ACM, 27, 7 (July 1984), 703–718.
A. C. Yao. On Constructing Minimum Spanning Trees ink-Dimensional Spaces and Related Problems.SIAM Journal on Computing, 11, 4 (November 1982), 721–736.
Author information
Authors and Affiliations
Additional information
Communicated by C. K. Wong.
Support for the first author was provided in part by NSF Grant MCS-83-08806. Support for the second author was provided in part by NSF Grants MCS-81-05324 and DCR-84-03613, an NSF Presidential Young Investigator Award, an IBM research contract, and an IBM Faculty Development Award. Support for this research was also provided in part by an ONR and DARPA under Contract N00014-83-K-0146 and ARPA Order No. 4786. Equipment support was provided by NSF Grant MCS-81-218106.
Rights and permissions
About this article
Cite this article
Sedgewick, R., Vitter, J.S. Shortest paths in euclidean graphs. Algorithmica 1, 31–48 (1986). https://doi.org/10.1007/BF01840435
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01840435