Re: [Boost-users] A* heuristic

Subject: Re: [Boost-users] A* heuristic
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-12-21 14:58:41

On Wed, 21 Dec 2011, giridhar wrote:

> Hello All,
> 
>       I have a question about defining A* heuristic. I am trying to implement an algorithm in a paper using BGL.
> Here authors have used A* Dijkstra's to calculate shortest route with an additional constraint of route length
> should be no longer than a threshold value t.
> 
> I think due to this threshold constraint they are using A* instead of normal Dijkstra's algorithm.
> 
> I came to know A* is already there in Boost Graph Library. I just have a basic knowledge about A* algorithm that it
> finds the shortest route based on the  heuristic H.
> 
> I tried to look into the example in BGL, but I did not get any hint to define a heuristic. Can anybody give me some
> hints or some useful links of how can I define a heuristic for this particular scenario of finding the shortest path
> between nodes that is no longer than threshold t through A* Dijkstra. This would be really helpful for me to proceed
> further.

The heuristic is something that is application-specific; there is no 
single heuristic for all graphs.  If your graph is something like a road 
network, there are distance-based heuristics you can use.  See 
http://en.wikipedia.org/wiki/A* and 
http://en.wikipedia.org/wiki/Admissible_heuristic for more information and 
examples.  If you don't have a heuristic available, Dijkstra's algorithm 
is likely to be preferable, especially if your graph is not tree-like 
(many paths converge to a single node).

-- Jeremiah Willcock