Re: [Boost-bugs] [Boost C++ Libraries] #4731: Documentation for dijkstra shortest path is wrong

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #4731: Documentation for dijkstra shortest path is wrong
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2010-10-14 14:35:35

#4731: Documentation for dijkstra shortest path is wrong
------------------------------------------------------+---------------------
  Reporter:  Markus Pilman <mpilman@…>                |       Owner:  asutton                                               
      Type:  Bugs                                     |      Status:  reopened                                              
 Milestone:  To Be Determined                         |   Component:  graph                                                 
   Version:  Boost 1.44.0                             |    Severity:  Problem                                               
Resolution:                                           |    Keywords:  bgl graph dijaksta shortest path minimum spanning tree
------------------------------------------------------+---------------------
Changes (by andresbuehlmann@…):

  * status:  closed => reopened
  * resolution:  fixed =>

Comment:

 The term "search tree" used in the current fix is misleading/imprecise
 depending how you define "search tree". Either use a term like "fully
 relaxed search tree" or another term like "spanning tree describing all
 shortest paths from the specified start vertex".

 Observe that the spanning tree encoded in the predecessor map describes
 the shortest path to every vertex in the graph from the defined start
 vertex. This is usually NOT equal to the "search tree" describing the
 order in which dijkstra explored the edges (without applying relaxation to
 this tree).

 To observe the difference between "fully relaxed search tree" and "search
 tree" the following example:

 Given a graph on vertices {0, 1, 2} and edges (0, 1, 2), (1, 2, 4), (0, 2,
 3) where the format is (start point, end point, weight).

 For running dijkstra on it with start vertex 1:
 * The "Search tree" in my eyes would be (1, 1, 0) (to be read as the
 predecessor map)
 * The predecessor map (result of dijkstra) is: (1, 1, 1)

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