### 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 language | English (US) |
---|---|

Title of host publication | Annual Symposium on Foundations of Computer Science (Proceedings) |

Publisher | IEEE |

Pages | 417-424 |

Number of pages | 8 |

ISBN (Print) | 081860591X |

State | Published - Dec 1 1984 |

Externally published | Yes |

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