Ticket #4737 (closed Bugs: fixed)

Opened 7 years ago

Last modified 7 years ago

Documentation for Prim MST concerning distance_map is wrong

Reported by: nicoe@… Owned by: asutton
Milestone: To Be Determined Component: graph
Version: Boost 1.44.0 Severity: Problem
Keywords: Cc:


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


Example.cpp Download (1.2 KB) - added by nicoe@… 7 years ago.

Change History

Changed 7 years ago by nicoe@…

comment:1 Changed 7 years ago by jewillco

  • Status changed from new to closed
  • Resolution set to fixed

(In [65963]) Fixed documentation of distance map; fixes #4737

comment:2 Changed 7 years ago by jewillco

(In [66093]) Merged changes r65193, r65939, r65963, and r65964 from trunk; refs #4731, #4737


Add a comment

Modify Ticket

Change Properties
<Author field>
as closed
The resolution will be deleted. Next status will be 'reopened'

E-mail address and user name can be saved in the Preferences.

Note: See TracTickets for help on using tickets.