[pgrouting-users] A* vs. Dijkstra and the nature of the A* implementation

[Stephen V. Mather]

> In general, A* is much more efficient because it does not have to solve
> the whole network as Dijkstra has to. Take the simple case of the start
> node in a center of a square region with a uniform distribution of nodes
> and edges over the square. If you route from the center to one of the
> corners, A* only needs to look at enough edges to get to the destination
> node and it can stop. While Dijkstra will solve the whole network.

Cool.  That was my interpretation.

> But for large networks, the overwhelming cost might to be build the
> graph in the first place. I don't have hard numbers handy about I think
> that fetching the edges and building the graph cost more than solving it.

My hunch was that building the graph for our case is the more expensive operation due to io.

> > Also, regarding A* implementation, is it strict, or is there any way to
> > relax the admissibility criterion as currently implemented?
> 
> There are not any controls that I am aware of.

Cool.

> You might want to look at TRSP. This is going to replace shooting star
> which is seriously broken and noone know how it is supposed to work.
> TRSP allow you to select an edge and an offset along that edge as the
> start and end point. This is critical is you want your start or end
> point to be on a segment that is a one way street. For ample it is
> possible to have both the start and the end on the same segment like:
> 
>      ---o-->--E--->--------S----o----

Ah, so I wouldn't have to create a temporary node because I'm dealing with ways?

> Let me know if your need more information.

Will do.  More homework for me... .

:)

Best,
Steve

  Stephen V. Mather
GIS Manager
(216) 635-3243 (Work)
clevelandmetroparks.com