A simple method for finding the shortest paths in Euclidean graphs (where vertices are points in a Euclidean space and edge weights are distances between points) is analyzed. For many graph models, the running time of the algorithm for finding 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(V log V plus E) required by the classical (Dijkstra) algorithm.
|Original language||English (US)|
|Title of host publication||Annual Symposium on Foundations of Computer Science (Proceedings)|
|Number of pages||8|
|State||Published - Dec 1 1984|
All Science Journal Classification (ASJC) codes
- Hardware and Architecture