Campus Event Calendar

Event Entry

What and Who

Real Shortest Paths in Real Time

Holger Bast
Max-Planck-Institut für Informatik - D 1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5  
AG Audience

Date, Time and Location

Tuesday, 4 April 2006
30 Minutes
E1 4


Joint work with Domagoj and Stefan F. Work in progress with a nice idea and a nice demo.

It's about answering shortest path queries on (real) road networks in log n time, with an O(n) time and O(n) space preprocessing, where n is the number of nodes. These three bounds have not been simultaneously attained so far.

The constants are such that for the road map of Germany (about 4 million nodes) query times are below 1 millisecond, and preprocessing takes a couple of hours using about 2 GB of main memory of a standard PC. In comparison, a standard Dijkstra computation for this map takes a couple of seconds.


Holger Bast
--email hidden
passcode not visible
logged in users only

Holger Bast, 04/04/2006 01:58
Holger Bast, 04/03/2006 11:15 -- Created document.