TY - GEN
T1 - Shortest paths in euclidean graphs
AU - Sedgewick, Robert
AU - Vitter, Jeffrey Scott
N1 - Funding Information:
* 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 Grant MCS-81-05324, by an IBM research contract, and by an IBM Faculty D e velopment Award, Support for this research was abo provided in part by oNR and DARpA under Contract I\rOOO14-83-K-0146 and ARPA Order No. 4786. Equip-ment support waa provided by NSF Grant MCS-81-218106.
Publisher Copyright:
© 1984 IEEE.
PY - 1984
Y1 - 1984
N2 - We analyze a simple method for finding shortest paths in Euclidean graphs (where vertices are points in a Euclidean space and edge weights are distances between points). For many graph models, the 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 (V log V + E) required by the classical (Dijkstra) algorithm.
AB - We analyze a simple method for finding shortest paths in Euclidean graphs (where vertices are points in a Euclidean space and edge weights are distances between points). For many graph models, the 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 (V log V + E) required by the classical (Dijkstra) algorithm.
UR - http://www.scopus.com/inward/record.url?scp=85115262048&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115262048&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85115262048
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 417
EP - 424
BT - 25th Annual Symposium on Foundations of Computer Science, FOCS 1984
PB - IEEE Computer Society
T2 - 25th Annual Symposium on Foundations of Computer Science, FOCS 1984
Y2 - 24 October 1984 through 26 October 1984
ER -