Shortest paths in Euclidean graphs (Q1087335)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Shortest paths in Euclidean graphs |
scientific article; zbMATH DE number 3988732
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Shortest paths in Euclidean graphs |
scientific article; zbMATH DE number 3988732 |
Statements
Shortest paths in Euclidean graphs (English)
0 references
1986
0 references
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.
0 references
analysis of algorithms
0 references
graph algorithm
0 references
Dijkstra's algorithm
0 references
priority queue
0 references
