Finding distances in graphs where shortest path has a large number of nodes I was wondering what is the most efficient way to find the shortest distances between all pairs of vertices in a graph where the shortest path between those vertices has length $\geq L$.  The only way I know of so far is to choose a smaller "hitting set" $B$ such that each long shortest path contains at least one node from $B$ with high probability.  Then you can find all distances from nodes in $B$ to all nodes in the graph, and get $d(u, v) = \min_b d(u, b) + d(b, v)$.

Are there any faster methods?

Thanks!
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.