Hello. I think will be better and faster, when you send message to maintainers of Boost.Graph directly. Also you can prepare your pull request with fixed code or documentation and do pull request. Link to GitHub repo: https://github.com/boostorg/graph -- Best regards, Alexander Zaitsev 12.07.2016, 10:45, "Nick Lamprianidis" :

For the A* algorithm holds that when a new vertex v is reached through a shorter path, then v is added to the open set. But looking at the boost graph's A* implementation, which is based on the BFS algorithm, one can see that a target vertex is added to the priority queue, regardless of whether the relevant edge is being relaxed.

This creates the following situation: The execution starts and you get to a point where you know you cannot reach the goal: no vertices with finite cost in the priority queue. Normally, you would expect that the priority queue is empty and thus the execution ends. Instead, the execution continues, since the priority queue is filled with all those vertices (with infinite cost) that got added for no reason.

In an application where the state of a target vertex v gets set when an associated edge is being relaxed, a problem arises. In the situation mentioned above, uninitialized vertices reach the visitor's examine_vertex method. Unless you know what's really happening, so you can take care to add a test condition to exit, it leaves you wondering what's going wrong.

I propose that you either change the implementation or at least update the documentation (pseudocode).

-- Nick Lamprianidis http://paign10.me

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

--  С уважением, Зайцев Александр.