3 ms·
Nobody stores all shortest paths, that's just silly. With some rather simple preprocessing you can answer shortest paths queries on the US road network in micro
by adrianN 11y ago
Nobody stores all shortest paths, that's just silly. With some rather simple preprocessing you can answer shortest paths queries on the US road network in microseconds [1], with preprocessing time of less than a day on a single machine. Surely Google can scale that up to larger graphs.
[1]http://people.mpi-inf.mpg.de/~dmatijev/papers/DIMACS06.pdf http://people.mpi-inf.mpg.de/~dmatijev/papers/DIMACS06.pdf