id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
4731,Documentation for dijkstra shortest path is wrong,Markus Pilman <mpilman@…>,Andrew Sutton,"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.",Bugs,closed,To Be Determined,graph,Boost 1.44.0,Problem,fixed,bgl graph dijaksta shortest path minimum spanning tree,