The FastMap Algorithm for Shortest Path Computations
  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.
