Shortest Paths in Road Networks: From Practice to Theory and Back
Daniel Delling, Andrew V. Goldberg, Renato F. Werneck · it - Information Technology · 2011
Abstract We illustrate the use of the scientific method in algorithmics by surveying recent developments in route planning on road networks. Several speed-up techniques proposed in the past decade are intuitive, elegant, and very efficient in practice, but lacked a theoretical explanation of their observed performance. By introducing a formal definition of road networks, recent theoretical work closed this gap. It also predicted that a previously untested algorithm should be even faster, which was confirmed by a subsequent implementation.