Providing directions instantly online has until recently meant that navigational mapping programs, such as MapQuest and Google Maps, often simplify the problem by not considering every possible route to a destination. Scientists at the University of Karlsruhe in Germany have designed a computer application that can quickly calculate the most expedient of all possible driving routes without the need for excessive computation.
Dominik Schultes, one of the project's scientists, designed the program around a simple premise: driving somewhere usually requires crossing major intersections that are sparsely interconnected. Figuring the best route occurs by precomputing the connections between a starting point (or destination) and its nearest major intersections and between all locations where major routes cross each other's paths—so-called transit nodes. When this parsimonious algorithm was tested on densely routed maps of western Europe and the U.S., the route calculations improved by a factor of 100.