Preprocessing Sparse, Directed Non-Planar Graphs for Faster Shortest Path I'm trying to preprocess a very large and sparse directed graph in order to do faster shortest path searches.  The vertices have no natural distance function, and the edges are unweighted.

One thought I had was to try and use a force directed graph layout algorithm to project the graph into space.  This way I could use cartesian distance for ASTAR and maybe get some improvements.

Constraint: There are so many vertices that any solution requiring a data with $O(n^2)$ space isn't viable.  However $O(n)$ space is fine, which is what made me think about assigning spacial coordinates to each vertex and doing distance calculations.

Any thoughts on this idea or others?

Thanks,

- Dan

UPDATE: For anyone interested, here's a paper that discusses my initial idea exactly: http://www.siam.org/meetings/alenex05/papers/02d.wagner.pdf
There have been many results on distance oracles and approximate distance oracles for directed graphs. A distance oracle for a graph is a data structure which can be queried on any pair of vertices (u,v) and returns the distance from u to v. It might also return the path realizing this distance. A good place to start (for the undirected case) would be:

Mikkel Thorup and Uri Zwick. Approximate distance oracles.
Journal of the ACM, 52(1):1–24, 2005.

For the directed case you should check out:

Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick,
Reachability and distance queries via 2-hop labels
SIAM Journal on Computing 32, 1338--1355 (2003).

Some other works also manage to construct such data structures which are also dynamic, that is, it is possible to update the data structure with changes to the graph.