Re: [Boost-bugs] [Boost C++ Libraries] #7398: edge weights equal to distance_inf not correctly supported in dijkstra

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #7398: edge weights equal to distance_inf not correctly supported in dijkstra
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2012-09-21 15:50:27

#7398: edge weights equal to  distance_inf not correctly supported in dijkstra
--------------------------------------------------+-------------------------
  Reporter:  Alex Hagen-Zanker <ahh34@…>          |       Owner:  jewillco       
      Type:  Bugs                                 |      Status:  closed         
 Milestone:  To Be Determined                     |   Component:  graph          
   Version:  Boost 1.52.0                         |    Severity:  Problem        
Resolution:  invalid                              |    Keywords:  dijkstra, relax
--------------------------------------------------+-------------------------

Comment (by Alex Hagen-Zanker <ahh34@…>):

 Ok.It does not seem like a very robust way of ignoring edges. It feels
 wrong to me to not filter out non-edges at the outer-loop of the algorithm
 but to do at the most detailed levels of computation. Even having to
 redefine the plus operations. Do you not use filtered_graph for that? How
 about measures like in-degree and out-degree, won't you get the wrong
 numbers? How about the visitors that are called along the way won't they
 get issued with mis-information? For instance vertices may now be
 discovered even when they are not reachable. The documentation says that
 "each reachable vertex is discovered exactly once". But it does not tell
 us that unreachable vertices may also be discovered.

 http://www.boost.org/doc/libs/1_51_0/libs/graph/doc/dijkstra_shortest_paths.html


 Anyway the use of edge weights invalidates quite a bit of my comments in
 #7387, but I suppose you figured that already.

 Sorry to ramble, it just seems very wrong to me.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/7398#comment:3>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.