To be clear, "turn-by-turn navigation" was an example of a query that happens on a fairly static graph: the road network. If the driver misses the turn, that just triggers another query on a static graph. I was not talking about needing to incorporate changes in connectivity, or in edge weights (due to e.g. road closures, or traffic updates).
Regarding "if you have even the slightest amount of time", no I don't think that's accurate. It's a trade-off between "offline" and "online" computation (sorry those words are so loaded, but they are often used in research on planning algorithms).
You could conceivably solve the All-Pairs Shortest Path for the road network offline, and then when you received a query online, you would be able to answer "immediately" by look-up table.
You could do nothing offline, and just run A* when you get a query. You won't be leveraging anything from the fact that the road network is fairly static.
Those are two endpoints of the trade-off spectrum, and approaches like contraction hierarchy lie in between.
Saying "contraction hierarchies supersedes A*" is kind of like saying "database indexing supersedes grep". If you're only going to grep a document once, it is not worth it to build an index. An index usually only helps if you will do multiple queries on the data.
Regarding "if you have even the slightest amount of time", no I don't think that's accurate. It's a trade-off between "offline" and "online" computation (sorry those words are so loaded, but they are often used in research on planning algorithms).
You could conceivably solve the All-Pairs Shortest Path for the road network offline, and then when you received a query online, you would be able to answer "immediately" by look-up table.
You could do nothing offline, and just run A* when you get a query. You won't be leveraging anything from the fact that the road network is fairly static.
Those are two endpoints of the trade-off spectrum, and approaches like contraction hierarchy lie in between.
Saying "contraction hierarchies supersedes A*" is kind of like saying "database indexing supersedes grep". If you're only going to grep a document once, it is not worth it to build an index. An index usually only helps if you will do multiple queries on the data.