Preprocessing Sparse, Directed Non-Planar Graphs for Faster Shortest Path
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.