Shortest paths in euclidean graphs

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