search

bmwcarit / barefoot

Java map matching library for integrating the map into software and services with state-of-the-art online and offline map matching that can be used stand-alone and in the cloud.
Apache License 2.0
664 stars 185 forks source link

A* vs. Dijkstra #124

Open geoHeil opened 5 years ago

geoHeil commented 5 years ago

Why did you choose Dijkstra over A*?

smattheis commented 5 years ago

Sorry for the delay. For short routing distances as we have it in map matching even for 3 min sampling intervals, we encountered more overhead for the calculation of the heuristic distance function than a benefit from "guiding" the route search. Further, our Dijkstra implementation uses a single-source-multiple-target approach to save time/workload when we calculate some number of similar routes between matching candidates. This is not straight-forward with A* because for each target we must maintain a different value of the heuristic function per edge.