# Approximate Distance Oracle Flashcards

What is the functionality of the **approximate distance oracle?**

**What are its parameters?**

**Give examples of naive solutions.**

Given weighted and undirected graph, we want to compute a small data structure that can answer distance questions efficiently and with mul-approximation.

**Parameters:**

**S - size of the data structure**

**Q - Question time**

**t - quality of approximation**

**p - inital computation tim**

Assume we want to compute all pairs initialy.

Assume we don’t want to compute anything initially.

What are the values of S,Q,T,P for each case?

S = n^2, Q = 1, T = 1, P = n^3

S = n^2, q = n^2, Q = 1, P = 1

Write definitions

and space

Describe query(u,v)

Define C(u) and mention the two observations

Write the efficient algorithm for finding the path to B(u)