# Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling

arXiv: https://arxiv.org/abs/1304.4661 · HTML: https://mlsanity.com/paper/1304.4661/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Apr 2013.

## Built on by (most cited first, 7 of 7)

- [Hierarchical Position Embedding of Graphs with Landmarks and Clustering for Link Prediction](https://mlsanity.com/paper/2402.08174/) (2024)
- [Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach](https://mlsanity.com/paper/2509.05129/) (2025)
- [Three Pillars Towards Next-Generation Routing System](https://mlsanity.com/paper/2409.11412/) (2024)
- [Landmark-Based Node Representations for Shortest Path Distance Approximations in Random Graphs](https://mlsanity.com/paper/2504.08216/) (2025)
- [Skeleton-Guided Learning for Shortest Path Search](https://mlsanity.com/paper/2508.02270/) (2025)
- [AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT](https://mlsanity.com/paper/2604.20744/) (2026)
- [TTFT-Aware Graph Chain-of-Thought:Distance-Indexed Neural A* for Low-Hallucination Multi-Hop Medical Reasoning](https://mlsanity.com/paper/2606.23108/) (2026)

## Abstract (arXiv)

We propose a new exact method for shortest-path distance queries on large-scale networks. Our method precomputes distance labels for vertices by performing a breadth-first search from every vertex. Seemingly too obvious and too inefficient at first glance, the key ingredient introduced here is pruning during breadth-first searches. While we can still answer the correct distance for any pair of vertices from the labels, it surprisingly reduces the search space and sizes of labels. Moreover, we show that we can perform 32 or 64 breadth-first searches simultaneously exploiting bitwise operations. We experimentally demonstrate that the combination of these two techniques is efficient and robust on various kinds of large-scale real-world networks. In particular, our method can handle social networks and web graphs with hundreds of millions of edges, which are two orders of magnitude larger than the limits of previous exact methods, with comparable query time to those of previous methods.