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