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 14:42: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
--------------------------------------------------+-------------------------
Changes (by jewillco):

  * status:  new => closed
  * resolution:  => invalid

Comment:

 This is the intended behavior -- the graph logically is assumed to have
 all edges, with some of those (the ones that are not connected in the
 graph's topology) having infinite weight.  See
 http://cpsc.ualr.edu/srini/DM/chapters/review5.3.html for an example; it
 is commonly used for shortest path algorithms.  Thus, infinite-weight
 edges are treated as not existing at all since they are the same in the
 matrix representation.  If you want an edge to be treated as active, give
 it a weight less than infinity.  A scheme such as the one described at
 http://tex.stackexchange.com/questions/21022/what-is-the-difference-

 between-fil-and-fill will give you multiple levels of "infinity" to use
 for edge weights and path lengths.

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