Shortest paths in euclidean graphs |
| |
Authors: | Robert Sedgewick Jeffrey Scott Vitter |
| |
Affiliation: | 1. Department of Computer Science, Brown University, 02912, Providence, RI, USA
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|