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

Subject: Re: [boost] [graph] A* implementation doesn't follow the algorithm
From: Зайцев Александр (zamazan4ik_at_[hidden])
Date: 2016-07-12 07:20:43

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" <paign10.ln_at_[hidden]>:
> 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
--Â 
С уважением, Зайцев Александр.