Shortest paths in euclidean graphs

Robert Sedgewick; Jeffrey Scott Vitter

doi:10.1007/BF01840435

Shortest paths in euclidean graphs

Robert Sedgewick, Jeffrey Scott Vitter

Research output: Contribution to journal › Article › peer-review

71 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 language	English (US)
Pages (from-to)	31-48
Number of pages	18
Journal	Algorithmica
Volume	1
Issue number	1
DOIs	https://doi.org/10.1007/BF01840435
State	Published - Mar 1 1986
Externally published	Yes

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

Access to Document

10.1007/BF01840435

Cite this

@article{f73de47e7b7e4125959f0b21681967eb,

title = "Shortest paths in euclidean graphs",

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.",

keywords = "Analysis of Algorithms, Dijkstra's algorithm, Euclidean, Graph algorithm, Heuristic, Priority queue, Shortest path",

author = "Robert Sedgewick and Vitter, {Jeffrey Scott}",

year = "1986",

month = mar,

day = "1",

doi = "10.1007/BF01840435",

language = "English (US)",

volume = "1",

pages = "31--48",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Shortest paths in euclidean graphs

AU - Sedgewick, Robert

AU - Vitter, Jeffrey Scott

PY - 1986/3/1

Y1 - 1986/3/1

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 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.

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 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.

KW - Analysis of Algorithms

KW - Dijkstra's algorithm

KW - Euclidean

KW - Graph algorithm

KW - Heuristic

KW - Priority queue

KW - Shortest path

UR - http://www.scopus.com/inward/record.url?scp=0022953574&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0022953574&partnerID=8YFLogxK

U2 - 10.1007/BF01840435

DO - 10.1007/BF01840435

M3 - Article

AN - SCOPUS:52449147619

SN - 0178-4617

VL - 1

SP - 31

EP - 48

JO - Algorithmica

JF - Algorithmica

IS - 1

ER -

Shortest paths in euclidean graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this