4 ms·
Does google maps use something like this? I imagine all pairs is too expensive, but the topology should be fairly consistent over time
by Jadrago 2y ago
Does google maps use something like this? I imagine all pairs is too expensive, but the topology should be fairly consistent over time
- urbandw311er 2y agoGoogle maps uses something called contraction hierarchies
- DennisL123 2y agoWithout knowing what they actually use, I feel comfortable to state that the industry has moved on from Contraction Hierarchies to somewhat more flexible techniques. These allow you to take traffic information and road closures, and user preferences, and whatnot into account without requiring a full re-processing of the input data with each traffic update. The state of the art is a two-step preprocessing that first decomposes the road network into cells, and then processes these cells independently. Sometimes it goes by the name of customisable route planning, sometimes it is called multi-level Dijkstra.
- ahoka 2y agoOne trick we used when I was in the transportation business is to pre-calculate the distances between border crossings and gas stations.
- DennisL123 2y agoStoring 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.