Subject: [Boost-commit] svn:boost r80637 - trunk/libs/graph/doc
From: jewillco_at_[hidden]
Date: 2012-09-22 15:21:40
Author: jewillco
Date: 2012-09-22 15:21:39 EDT (Sat, 22 Sep 2012)
New Revision: 80637
URL: http://svn.boost.org/trac/boost/changeset/80637
Log:
Added wording that infinite-weight edges are not guaranteed to work correctly; fixes #7398
Text files modified:
trunk/libs/graph/doc/dijkstra_shortest_paths.html | 4 +++-
trunk/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html | 14 ++++----------
2 files changed, 7 insertions(+), 11 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 2012-09-22 15:21:39 EDT (Sat, 22 Sep 2012)
@@ -330,7 +330,9 @@
<blockquote>
The <tt>inf</tt> object must be the greatest value of any <tt>D</tt> object.
That is, <tt>compare(d, inf) == true</tt> for any <tt>d != inf</tt>.
- The type <tt>D</tt> is the value type of the <tt>DistanceMap</tt>.<br>
+ The type <tt>D</tt> is the value type of the <tt>DistanceMap</tt>. Edges
+ are assumed to have a weight less than (using <tt>distance_compare</tt> for
+ comparison) this value.<br>
<b>Default:</b> <tt>std::numeric_limits<D>::max()</tt><br>
<b>Python</b>: Unsupported parameter.
Modified: trunk/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html
==============================================================================
--- trunk/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html (original)
+++ trunk/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html 2012-09-22 15:21:39 EDT (Sat, 22 Sep 2012)
@@ -69,7 +69,7 @@
</P>
<P>
- <tt>dijkstra_shortest_paths_no_color_map</tt> differs from the original <tt>dijkstra_shortest_paths</tt> algorithm by not using a color map to identify vertices as discovered or undiscovered. Instead, this is done with the distance map: a vertex <i>u</i> such that <i>distance_compare(distance_map[u], distance_infinity) == false</i> is considered to be undiscovered.
+ <tt>dijkstra_shortest_paths_no_color_map</tt> differs from the original <tt>dijkstra_shortest_paths</tt> algorithm by not using a color map to identify vertices as discovered or undiscovered. Instead, this is done with the distance map: a vertex <i>u</i> such that <i>distance_compare(distance_map[u], distance_infinity) == false</i> is considered to be undiscovered. Note that this means that edges with infinite weight will not work correctly in this algorithm.
</P>
<P>
@@ -116,10 +116,6 @@
<td valign="top">
<pre>
DIJKSTRA(<i>G</i>, <i>s</i>, <i>w</i>)
- <b>for</b> each vertex <i>u in V</i> <b>(This loop is not run in dijkstra_shortest_paths_no_color_map_no_init)</b>
- <i>d[u] := infinity</i>
- <i>p[u] := u</i>
- <b>end for</b>
<i>d[s] := 0</i>
INSERT(<i>Q</i>, <i>s</i>)
<b>while</b> (<i>Q != Ø</i>)
@@ -141,10 +137,6 @@
<td valign="top">
<pre>
-initialize vertex <i>u</i>
-
-
-
discover vertex <i>s</i>
@@ -293,7 +285,9 @@
<blockquote>
The <tt>distance_infinity</tt> object must be the greatest value of any <tt>D</tt> object.
That is, <tt>distance_compare(d, distance_infinity) == true</tt> for any <tt>d != distance_infinity</tt>.
- The type <tt>D</tt> is the value type of the <tt>DistanceMap</tt>.<br>
+ The type <tt>D</tt> is the value type of the <tt>DistanceMap</tt>. All edges
+ are assumed to have weight less than (by <tt>distance_compare</tt>) this
+ value.<br>
<b>Default:</b> <tt>std::numeric_limits<D>::max()</tt><br>
</blockquote>