Re: [Boost-users] A* heuristic

Subject: Re: [Boost-users] A* heuristic
From: Stephen Woodbridge (woodbri_at_[hidden])
Date: 2011-12-21 15:08:23

On 12/21/2011 2:53 PM, 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.

Wait, I'm confused. Is your threshold t a cutoff distance? So what to 
you want to happen when you get to "t", stop the search? On input, do 
you specify the destination node?

If there is no destination node then it is dijkstra, the distance is the 
current cost to get to any given node as you explore the graph, ie the 
sum of the costs on the predecessors. And all you are doing is getting 
the path from the start node to all nodes in the graph where the path 
length is less then "t".

If this is your case, then one way to handle this in Boost is to create 
a visitor and check the path length as each node is explored and if it 
is greater than "t" do not node add any outbound links/nodes to the queue.

-Steve