I want to make my A-Star fast, by using heuristics. At the moment it is very slow and even slower than my Dijkstra. I thougt A-Star is in the worst case as fast as Dijkstra. I convert my OSM bounding box wiht osm2po to a postgresql database with postgis support and then I do my routing with java on android. Do I have to consider something in the osm2po configuration file to get the right weight? For the heuristics calculation I use the Manhattan distance.

  • You should use a different heuristic for the distance otherwise you're overestimating the distance which makes the results inexact - why not use the air distance (which is natural when using OSM data)? And: A* should be faster than Dijkstra otherwise something is wrong.
    – Karussell
    Jun 25 '13 at 6:43
  • You mean Euclidean distance? Jun 25 '13 at 7:29
  • yes (necessary fill for SE)
    – Karussell
    Jun 25 '13 at 10:02

Mostly an AStar is faster than a Dijkstra. But it's a superstition that it is always faster. Imagine an area shaped like a circle. Routing from the center to a border point lets expand a Dijkstra to the worst case whereby an AStar shows its optimal behavior. Driving the reverse route an AStar will expand to almost the same worst case. But in addition, an AStar has to calculate the distance to the target (using at least the Euclidean Distance calculation) which is a very expensive operation. In this case, it would be indeed slower than a Dijkstra. Nevertheless, you cannot use the Manhattan Distance. The Manhattan Distance is a good filter for expensive Distance calculations, but no alternative.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.