Note to users. If you're seeing this message, it means that your browser cannot find this page's style/presentation instructions -- or possibly that you are using a browser that does not support current Web standards. Find out more about why this message is appearing, and what you can do to make your experience of our site the best it can be.

Science 27 April 2007:
Vol. 316. no. 5824, p. 566
DOI: 10.1126/science.1137521
Prev | Table of Contents | Next

Brevia

Fast Routing in Road Networks with Transit Nodes

Holger Bast,1 Stefan Funke,1 Peter Sanders,2* Dominik Schultes2

When you drive to somewhere far away, you will leave your current location via one of only a few important traffic junctions. Starting from this informal observation, we developed an algorithmic approach, transit node routing, that allows us to reduce quickest path queries in road networks to a small number of table lookups. For road maps of Western Europe and the United States, our best query times improved over the best previously published figures by two orders of magnitude. This is also more than one million times faster than the best known algorithm for general networks.

1 Max-Planck-Institut für Informatik, 66123 Saarbrücken, Germany.
2 Universität Karlsruhe (TH), 76128 Karlsruhe, Germany.

* To whom correspondence should be addressed. E-mail: sanders{at}ira.uka.de

Read the Full Text

To Advertise     Find Products

Science. ISSN 0036-8075 (print), 1095-9203 (online)