[Routing] Graph libraries and A*

Alex Wilson alex_wilson at pobox.com
Wed Nov 21 07:41:31 GMT 2007


There is a fully-tested implementation of A* (as well as several other 
shortest path implementations) in the Boost C++ libraries (the Boost 
graph library), as well as a comprehensive framework for representing 
the graphs. It takes very little time to get A* up and running using 
these - and IMHO it is always preferable to use a good library (as long 
as it fits) rather than to code your own implementation - no need to 
reinvent the wheel. There are also python bindings for the library, for 
those who'd rather prototype in a scripting language - but with the 
benefit of a compiled implementation for the A* algo.

The BGL: http://www.boost.org/libs/graph/doc/table_of_contents.html
Python bindings: http://www.osl.iu.edu/~dgregor/bgl-python/  
An AStar example: http://www.boost.org/libs/graph/example/astar-cities.cpp

Alex

Nic Roets wrote:
>> Would it break anything to even use sqr(dx)+sqr(dy) instead of
>> sqrt(sqr(dx)+sqr(dy)) ?
>>     
>
> If dx is in degrees or radias, you'll end up with Dijkstra and if it's
> meters, the routing will be worse than my mom.
>
> If you want to get rid of the squareroot, you can try variations of
> the "taxi-cab" metric like |x|/2 + |y|/2 or max(|x|,|y|) also known as
> the l_1 and l_infinite norms.
>
> I see Jon when for all out great circle distances which is
> computationally intensive and theoretically more accurate, but
> practically much less important than penalizing right turns.
>
> The next level would be to cut the map into regions / tiles and
> precompute lower bounds on the shortest / fastest path. At run time
> those lower bounds are then fed into the heuristic. But that
> improvement will only improve the speed a few percent.
>
> If you have enough memory (say 100 bytes per segment) you can write a
> C version without hashing. Then the only "slow" part is the priority
> queue (heap).
>
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
>
>   





More information about the Routing mailing list