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?


  • 2
    $\begingroup$ What does "with high probability" mean? Is your algorithm randomized? $\endgroup$
    – Jeffε
    Commented May 3, 2014 at 0:58
  • $\begingroup$ Yep, that algorithm is randomized. $\endgroup$
    – Jessica
    Commented May 3, 2014 at 7:51

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.