On a small campus road network the heuristic search wins clearly on a single route, and loses most of that edge as the destination moves farther away.
The usual summary is that A star beats Dijkstra and you should just use it. Timings from an Android navigation prototype put a condition on that advice. The gap between the two algorithms is real, but it depends on how far the route has to travel.
The measurements come from a prototype running on a Google Nexus 6 with Android 7.0, working over a campus road network of 134 nodes and 154 edges. Queries were grouped by how close the start and end points were, which is what makes the result interesting.
The pattern follows from how the heuristic works. A star gains when the estimate can steer the search away from large parts of the graph. Over a short distance there is not much to steer away from, and the estimation cost takes a bigger share of the total.
Dijkstra solves a different problem. It finds the shortest path from one source to every other node in a single pass, so its work carries over when an app needs several destinations from the same origin. The authors suggest pre-caching routes with Dijkstra when the next destination can be predicted, and reserving the guided search for one off requests.
The honest conclusion for a working app is that neither number is uncomfortable on a graph this size. Both algorithms answer in milliseconds on hardware from a few years back. Where the difference starts to matter is at scale, or when an app fires many queries in a row.
There is also a design lesson that has little to do with either algorithm. The framework keeps road data on the device after the first fetch, so a route can be computed without waiting on the network. For how fast the app feels to use, that choice does more work than any milliseconds saved inside the search loop.
Pinandito, A., Kharisma, A.P., Perdana, R.S. (2018). Framework Design for Map-Based Navigation in Google Android Platform. Journal of Telecommunication, Electronic and Computer Engineering (JTEC), 10(1-8).
