<p>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 <a href="http://kaashoek.org/~petar/behind/oracles-zwick-stoc01.pdf" rel="nofollow">Thorup-Zwick, <em>Approximate Distance Oracles</em> (STOC 2001)</a>.</p>

<p>Distance oracles can offer constant (but approximate) look-up.</p>

CC BY-SA 3.0
2014-05-03T00:18:39.843Z
2014-05-03T00:18:39.843Z
John K.
<p>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)$.</p>

<p>Are there any faster methods?</p>

<p>Thanks!</p>

CC BY-SA 3.0
2014-05-03T00:58:05.393Z
What does "with high probability" mean? Is your algorithm randomized?
Jeffε
CC BY-SA 3.0
2014-05-03T07:51:23.470Z
Yep, that algorithm is randomized.
Jessica
<graph-algorithms>
Finding distances in graphs where shortest path has a large number of nodes
Jessica
# Finding distances in graphs where shortest path has a large number of nodes

(Asked by: username_0 on 2014-05-02)

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!

**Tags:** graph-algorithms

> **Comments:**
> **username_1**: What does "with high probability" mean? Is your algorithm randomized?  
> **username_0**: Yep, that algorithm is randomized.  

---

## 1 answers

### Answer by username_2 on 2014-05-03. Score: 2 | Accepted answer

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)](http://kaashoek.org/~petar/behind/oracles-zwick-stoc01.pdf).

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


---

