Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck
We present an algorithm to compute shortest paths on continental road networks with arbitrary metrics (cost functions). The approach supports turn costs, enables real-time queries, and can incorporate a new metric in a few seconds---fast enough to support real-time traffic updates and personalized optimization functions. The amount of metric-specific data is a small fraction of the graph itself, which allows us to maintain several metrics in memory simultaneously.
|Published in||Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11)|
|Series||Lecture Notes in Computer Science|