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 +V log V) required by the classical algorithm due to Dijkstra.

Original languageEnglish (US)
Pages (from-to)31-48
Number of pages18
JournalAlgorithmica
Volume1
Issue number1
DOIs
StatePublished - Mar 1 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Analysis of Algorithms
  • Dijkstra's algorithm
  • Euclidean
  • Graph algorithm
  • Heuristic
  • Priority queue
  • Shortest path

Fingerprint Dive into the research topics of 'Shortest paths in euclidean graphs'. Together they form a unique fingerprint.

Cite this