[DennisL123]

Storing the distances for all pairs is prohibitively expensive. Also, you'd need to store the path information as well. Fortunately, road networks exhibit a lot of hierarchical structure. For example, when going far away, you will almost certainly use the long-distance sub-network, i.e. highways. It is possible to exploit this in a preprocessing step that adds a linear amount of information, which is in turn used to speed up queries.