[pgrouting-dev] Ask how to use : Euclidean distance heuristic in A* in pgrouting

[Stephen Woodbridge]

On 7/9/2012 9:24 PM, Haruhi Suzumiya wrote:
> Good morning,
>
> Dear mr/mrs, :)
>
> I'm robi, my username is haruhi. I'm newbie in pgrouting.
> I want to try use euclidean distance heuristic in A* in pgrouting, may u
> give me tutorial how to change the heuristic and recompile it? :)
> Fyi, I'm use windows 7, postgre 1.8.4, pgRouting-1.02_pg-8.3.3 :)

Hi Robi,

The pgRouting package already supports A* and by definition it uses a 
euclidean distance heuristic. See the function shortest_path_astar(), 
there also may be some wrapper function with names like astar_sp_*

The wrapper function are just higher level convenience function.

There are a couple of tutorials around that probably have good examples 
of how to use the functions.

If you want to change the heuristic, then you will need to look at the 
Boost Graph code that is used to implement it. We don't have any 
documentation on the implementation, but there are a lot of docs on 
Boost Graph and you can get help from that list.

What I would do is write a wrapper for the Boost Graph code and reads a 
text file to input the graph, sets up the structures to pass the data to 
algorithm to run it and then prints out the results. You can do all this 
outside of the database which greatly simplifies debugging your changes. 
When you have it working the way you want, then it should be a clean 
drop in replacement for the existing code or you can clone the existing 
code and rename it for the new algorithm.

-Steve W