# The FastMap Algorithm for Shortest Path Computations

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jun 2017.

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

- [SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems](https://mlsanity.com/paper/2210.12547/) (2022)
- [FastMapSVM: Classifying Complex Objects Using the FastMap Algorithm and Support-Vector Machines](https://mlsanity.com/paper/2204.05112/) (2022)
- [Multi-Robot Path Planning Combining Heuristics and Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2306.01270/) (2023)
- [COL-Trees: Efficient Hierarchical Object Search in Road Networks](https://mlsanity.com/paper/2601.22183/) (2026)
- [Beyond Manual Planning: Seating Allocation for Large Organizations](https://mlsanity.com/paper/2602.05875/) (2026)
- [AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT](https://mlsanity.com/paper/2604.20744/) (2026)

## Abstract (arXiv)

We present a new preprocessing algorithm for embedding the nodes of a given edge-weighted undirected graph into a Euclidean space. The Euclidean distance between any two nodes in this space approximates the length of the shortest path between them in the given graph. Later, at runtime, a shortest path between any two nodes can be computed with A* search using the Euclidean distances as heuristic. Our preprocessing algorithm, called FastMap, is inspired by the data mining algorithm of the same name and runs in near-linear time. Hence, FastMap is orders of magnitude faster than competing approaches that produce a Euclidean embedding using Semidefinite Programming. FastMap also produces admissible and consistent heuristics and therefore guarantees the generation of shortest paths. Moreover, FastMap applies to general undirected graphs for which many traditional heuristics, such as the Manhattan Distance heuristic, are not well defined. Empirically, we demonstrate that A* search using the FastMap heuristic is competitive with A* search using other state-of-the-art heuristics, such as the Differential heuristic.