Finding distances in graphs where shortest path has a large number of nodes
If you accept approximations to the distances, you can take a look at distance oracles.  A good source is the paper on distance oracles by Thorup-Zwick, Approximate Distance Oracles (STOC 2001).

Distance oracles can offer constant (but approximate) look-up.