Subject: [Boost-commit] svn:boost r65964 - trunk/libs/graph/doc
From: jewillco_at_[hidden]
Date: 2010-10-14 15:02:04
Author: jewillco
Date: 2010-10-14 15:02:03 EDT (Thu, 14 Oct 2010)
New Revision: 65964
URL: http://svn.boost.org/trac/boost/changeset/65964
Log:
Clarified docs further; fixes #4731
Text files modified:
trunk/libs/graph/doc/dijkstra_shortest_paths.html | 7 +++++--
1 files changed, 5 insertions(+), 2 deletions(-)
Modified: trunk/libs/graph/doc/dijkstra_shortest_paths.html
==============================================================================
--- trunk/libs/graph/doc/dijkstra_shortest_paths.html (original)
+++ trunk/libs/graph/doc/dijkstra_shortest_paths.html 2010-10-14 15:02:03 EDT (Thu, 14 Oct 2010)
@@ -248,9 +248,12 @@
OUT: <tt>predecessor_map(PredecessorMap p_map)</tt>
<blockquote>
- The predecessor map records the edges in the search tree, the tree computed
+ The predecessor map records the edges in the shortest path tree, the tree computed
by the traversal of the graph. Upon completion of the algorithm, the edges
- <i>(p[u],u)</i> for all <i>u in V</i> are in the search tree. The search
+ <i>(p[u],u)</i> for all <i>u in V</i> are in the tree. The shortest path
+ from vertex <i>s</i> to each vertex <i>v</i> in the graph consists of the
+ vertices <i>v</i>, <i>p[v]</i>, <i>p[p[v]]</i>, and so on until <i>s</i> is
+ reached, in reverse order. The
tree is not guaranteed to be a minimum spanning tree. If <i>p[u] =
u</i> then <i>u</i> is either the source vertex or a vertex that is
not reachable from the source. The <tt>PredecessorMap</tt> type