[boost] [graph] A* implementation doesn't follow the algorithm

Subject: [boost] [graph] A* implementation doesn't follow the algorithm
From: Nick Lamprianidis (paign10.ln_at_[hidden])
Date: 2016-07-11 15:51:33

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