astar (#17) - How to use A* (#78) - Message List
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.
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)