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

Stephen Woodbridge woodbri at swoodbridge.com
Fri Apr 12 19:33:03 PDT 2013

```On 4/12/2013 9:07 PM, Stephen V. Mather wrote:
> Hi All,
>
> I'm curious about efficiency of A* vs Dijkstra in large networks.  If A*
> tends to follow the straight line nodes until/unless it finds an
> obstacle, for really large networks, under what conditions is A* a
> better choice than Dijkstra?

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.

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.

> 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.

> Finally, in using pgRouting for turn by turn, we have pre-chopped our
> network into short segments to ensure the nearest search node is close
> to the point we are searching so the directions start from a nearby
> point, not the nearest network intersection.

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----

In this case to get from S to E you have to exit right and find a route
back around to the E coming from the left. TRSP (Turn restricted
shortest path) is a little slower (not much) than dijkstra. You don't
have to give it turn restriction but if you have them they can be
supplied. There is a trivial test(s) in the sew-devel-2_0 branch for
trsp. It was developed under contract by a UK client and has been used
with restrictions and Navteq data. The test use the same graph with and
with out turn restriction. There is an image of the graph in
doc/static/images/

> For datasets as large as the one we are working with, this seems to
> result in a pretty high random IO tax.  I wondered if anyone has some
> boilerplate modifying the returned route, slicing the nearest ways to
> the beginning and end points with ST_ClosestPoint or similar?

I have done this, it is not that hard.

-Steve

> Thanks,
> Best,
> Steve
>
>
> http://sig.cmparks.net/cmp-ms-90x122.png Stephen V. Mather
> GIS Manager
> (216) 635-3243 (Work)
> clevelandmetroparks.com <http://www.clemetparks.com>
>
>
>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>

```