TY - GEN
T1 - Shortest paths in euclidean graphs
AU - Sedgewick, Robert
AU - Vitter, Jeffrey Scott
N1 - 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 -