astar (#17)  How to use A* (#78)  Message List
Hi,
I have some trouble using A* I think... I'm using both Dijkstra and A* on an edge table with 870706 entries. For A* I have created x1, y1, x2 and y2 values in the edge table consisting of the coordinates of the starting/ending point of the corresponding segment. Which is my first point where I'm not sure whether this is really correct as I could not really understand how the A* heuristic is working here. The second thing is, that calculating shortest paths on this edgeset takes for A* a little bit longer than for Dijkstra which confuses me also a little bit.

Message #313
Well, A* (hopefuly) searches through less number of edges (in worst case it is same number as Dijkstra) to find a shortest path, but it takes more time to load a data with x1, y1, x2, y2. A* needs this data to calculate a heuristic function value which, in our case, is just Euclidian distance between current and target vertices.
Nobody can tell that A* or Dijkstra is better or faster. They are both good, but for different cases. That's why we keep them both in pgRouting. If Dijkstra works better for your network  go ahead, use Dijkstra!
anton12/12/07 10:14:11 (3 years ago)