SHORTEST PATHS IN EUCLIDEAN GRAPHS.

Robert Sedgewick, Jeffrey Scott Vitter

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

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 languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE
Pages417-424
Number of pages8
ISBN (Print)081860591X
StatePublished - Dec 1 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Cite this

Sedgewick, R., & Vitter, J. S. (1984). SHORTEST PATHS IN EUCLIDEAN GRAPHS. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 417-424). IEEE.