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

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

#4731: Documentation for dijkstra shortest path is wrong
--------------------------------------------------------------------+-------
 Reporter:  Markus Pilman <mpilman@…>                               |       Owner:  asutton
     Type:  Bugs                                                    |      Status:  new    
Milestone:  To Be Determined                                        |   Component:  graph  
  Version:  Boost 1.44.0                                            |    Severity:  Problem
 Keywords:  bgl graph dijaksta shortest path minimum spanning tree  |  
--------------------------------------------------------------------+-------
 In the documentation for dijkstra_shortest_paths, you can read:

 "The predecessor map records the edges in the minimum spanning tree. Upon
 completion of the algorithm, the edges (p[u],u) for all u in V are in the
 minimum spanning tree."

 I would say, that this is wrong: Dijkstra won't give you a minimum
 spanning tree in all cases.

 One counterexample would be a undirected graph with the vertices (0,1,2)
 and the following edges (format is start,point, endpoint, weight):

 (0, 1, 2)
 (0, 2, 3)
 (1, 2, 4)

 This graph has only one minimum spanning tree with the predecessors map
 (2,0,2) - which is what you get with prim. If you execute dijkstra
 shortest path on this graph, you will get (2,2,2) - and this is not a
 minimum spanning tree (since the weight of this tree is 7, while the
 weight of the minimum spanning tree is 5).

 Find attached an example which calculates both algorithms on these two
 graphs. I really think this should be fixed in the documentation.

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