#4737 closed Bugs (fixed)
Documentation for Prim MST concerning distance_map is wrong
Reported by: | Owned by: | Andrew Sutton | |
---|---|---|---|
Milestone: | To Be Determined | Component: | graph |
Version: | Boost 1.44.0 | Severity: | Problem |
Keywords: | Cc: |
Description
In the documentation for prim_minimum_spanning_tree, you can read at distance_map:
The shortest path weight from the source vertex s to each vertex in the graph g is recorded in this property map. The shortest path weight is the sum of the edge weights along the shortest path.
I would say this is wrong. I claim that the prim_minimum_spanning_tree stores original edgeweights in the distance map. Precisely, an entry i in the distance map corresponds to the edgeweight of the edge from vertex i to its predecessor in the MST.
Example: Given a undirected graph on the vertex set {0,1,2} with edges (0,1,2), (0,2,3), (1,2,4) (to be read as vertex, vertex, weight). The output of prim MST called with parameters root_vertex(1) concerning the distance map is (2,0,3). According to the documentation it schould be (2,0,5).
See attached example for details
Attachments (1)
Change History (3)
Changed 7 years ago by
Attachment: | Example.cpp added |
---|
comment:1 Changed 7 years ago by
Resolution: | → fixed |
---|---|
Status: | new → closed |
(In [65963]) Fixed documentation of distance map; fixes #4737