If you wanted to know the shortest distance/path between two household addresses, which data structure(s) would you use to return the answer efficiently?
Say you are considering the set of all households in the United States (~100 million).
I am struggling to come up with a practical data structure considering the input size is so big. Dijkstra's seems too inefficient, but I'm guessing there is a way to preprocess the paths to make such a query possible.
This problem is well considered and learned in recent decades as every GPS device faces this problem.
In practice (AFAIK), the standard way of facing this problem is by the usage of distance oracles, which usually (or more correctly, used to) approximate the distance between every two nodes by keeping only a $k\times n$ distances tables for a well-selected $k$ vertices.
The lastest result I'm aware of, keep a data structure of size $O(kn^{1+1/k})$, answering queries in $O(1)$ time and giving a stretch (i.e. the return value $\delta$ is promised to suffice $d\leq \delta \leq d\cdot s$). of $2k-1$.
Alternatively, if you're looking for a stretch smaller than 2, I suggest looking at this paper.
