# 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!

• What does "with high probability" mean? Is your algorithm randomized? – Jeffε May 3 '14 at 0:58
• Yep, that algorithm is randomized. – Jessica May 3 '14 at 7:51