Shortest paths in Euclidean graphs (Q1087335)

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.