×

Shortest paths in Euclidean graphs. (English) Zbl 0611.68044

We analyze a simple method for finding shortest paths in Euclidean 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 with V vertices and E edges is shown to be O(V) as compared with \(O(E+V \log V)\) required by the classical algorithm due to Dijkstra.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Reading, MA: Addison-Wesley, Reading, MA · Zbl 0326.68005
[2] E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs.Numerishe Mathematik, 1 (1959). · Zbl 0092.16002
[3] Durrett, R., Oriented Percolation in Two Dimensions, The Annals of Probability, 12, 4, 999-1040 (1984) · Zbl 0567.60095 · doi:10.1214/aop/1176993140
[4] 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.
[5] 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. · Zbl 1412.68048
[6] 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.
[7] Golden, B. L.; Ball, M., Shortest Paths with Euclidean Distances: An Explanatory Model, Networks, 8, 297-314 (1978) · Zbl 0394.94040 · doi:10.1002/net.3230080404
[8] Gonnet, G. H., Expected Length of the Longest Probe Sequence in Hash Code Searching, Journal of the ACM, 28, 2, 289-304 (1981) · Zbl 0456.68067 · doi:10.1145/322248.322254
[9] Hart, P. E.; Nilsson, N. J.; Raphael, B., A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on Systems Science and Cybernetics, 4, 2, 100-107 (1968) · doi:10.1109/TSSC.1968.300136
[10] 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. · Zbl 0552.90089
[11] Loève, M., Probability Theory, Volume I. Graduate Texts in Mathematics (1977), New York: Springer-Verlag, New York · Zbl 0359.60001
[12] Sedgewick, R., Algorithms (1983), Reading, MA: Addison-Wesley, Reading, MA · Zbl 0529.68002
[13] Tarjan, R. E., Data Structures and Network Algorithms (1983), Philadelphia, PA: Society for Industrial and Applied Mathematics, Philadelphia, PA · Zbl 0584.68077
[14] Vitter, J. S., Faster Methods for Random Sampling, Communications of the ACM, 27, 7, 703-718 (1984) · Zbl 0595.65008 · doi:10.1145/358105.893
[15] Yao, A. C., On Constructing Minimum Spanning Trees ink-Dimensional Spaces and Related Problems, SIAM Journal on Computing, 11, 4, 721-736 (1982) · Zbl 0492.68050 · doi:10.1137/0211059
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.