Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck
We present a versatile and scalable algorithm for computing exact distances on real-world networks with tens of millions of arcs in real time. Unlike existing approaches, preprocessing and queries are practical on a wide variety of inputs, such as social, communication, sensor, and road networks. We achieve this by providing a unified approach based on the concept of 2-hop labels, improving upon existing methods. In particular, we introduce a fast sampling-based algorithm to order vertices by importance, as well as effective compression techniques.
We updated the TR in July 2014.
|Publisher||Microsoft Technical Report|