SHORTEST PATHS IN EUCLIDEAN GRAPHS.

Robert Sedgewick, Jeffrey Scott Vitter

Research output: Contribution to journalArticlepeer-review

59 Scopus citations

Abstract

We analyze a simple method for finding shortest paths in Euclidean 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 with V vertices and E edges is shown to be O(V) as compared with O(E plus V log V) required by the classical algorithm due to E. W. Dijkstra.

Original languageEnglish (US)
Pages (from-to)31-48
Number of pages18
JournalAlgorithmica (New York)
Volume1
Issue number1
StatePublished - 1986

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Applied Mathematics
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'SHORTEST PATHS IN EUCLIDEAN GRAPHS.'. Together they form a unique fingerprint.

Cite this