Goal Directed Shortest Path Queries Using Precomputed Cluster Distances | Zendy

Jens Maue | Zendy; Peter Sanders | Zendy; Domagoj Matijević | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Goal Directed Shortest Path Queries Using Precomputed Cluster Distances

Author(s) -

Jens Maue,

Peter Sanders,

Domagoj Matijević

Publication year - 2006

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-34597-3

DOI - 10.1007/11764298_29

Subject(s) - computer science , shortest path problem , path (computing) , cluster (spacecraft) , dijkstra's algorithm , theoretical computer science , algorithm , programming language , graph

We demonstrate how Dijkstra's algorithm for shortest path queries can be accelerated by using precomputed shortest path distances. Our approach allows a completely flexible tradeoff between query time and space consumption for precomputed distances. In particular, sublinear space is sufficient to give the search a strong “sense of direction”. We evaluate our approach experimentally using large, real-world road networks.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research