We study the problem of finding point-to-point shortest paths in a setting where preprocessing is allowed. We are interested in exact algorithms only, and our focus is on road networks. Our algorithms use several different strategies to speed up the queries. First, we use A* search to direct the search towards the goal. Second, we use the notion of "reach" to identify and prune local intersections.
Third, we add shortcuts to the graph to reduce the number of highway (i.e., non-local) edges. Our best query algorithm is thousands of times faster than Dijkstra's algorithm on the road networks of the United States and Western Europe, each with roughly 20 million vertices. This is joint work with Andrew Goldberg, Chris Harrelson, and Haim Kaplan.
Date and Time
Wednesday November 15, 2006 4:15pm -
5:45pm
Location
Computer Science Small Auditorium (Room 105)
Event Type
Speaker
Renato Werneck
Host
Robert Tarjan