ceph/src/boost/libs/graph/doc/bellman_ford_shortest.html

   1 <HTML>
   2 <!--
   3      Copyright (c) Jeremy Siek 2000
   4
   5      Distributed under the Boost Software License, Version 1.0.
   6      (See accompanying file LICENSE_1_0.txt or copy at
   7      http://www.boost.org/LICENSE_1_0.txt)
   8   -->
   9 <Head>
  10 <Title>Bellman Ford Shortest Paths</Title>
  11 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
  12         ALINK="#ff0000">
  13 <IMG SRC="../../../boost.png"
  14      ALT="C++ Boost" width="277" height="86">
  15
  16 <BR Clear>
  17
  18
  19 <H1><A NAME="sec:bellman-ford"></A><img src="figs/python.gif" alt="(Python)"/>
  20 <TT>bellman_ford_shortest_paths</TT>
  21 </H1>
  22
  23 <P>
  24 <PRE>
  25 <i>// named paramter version</i>
  26 template &lt;class <a href="./EdgeListGraph.html">EdgeListGraph</a>, class Size, class P, class T, class R&gt;
  27 bool bellman_ford_shortest_paths(const EdgeListGraph&amp; g, Size N,
  28   const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>);
  29
  30 template &lt;class <a href="./VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a>, class P, class T, class R&gt;
  31 bool bellman_ford_shortest_paths(const VertexAndEdgeListGraph&amp; g,
  32   const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>);
  33
  34 <i>// non-named parameter version</i>
  35 template &lt;class <a href="./EdgeListGraph.html">EdgeListGraph</a>, class Size, class WeightMap,
  36           class PredecessorMap, class DistanceMap,
  37           class <a href="http://www.sgi.com/tech/stl/BinaryFunction.html">BinaryFunction</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>,
  38           class <a href="./BellmanFordVisitor.html">BellmanFordVisitor</a>&gt;
  39 bool bellman_ford_shortest_paths(EdgeListGraph&amp; g, Size N,
  40   WeightMap weight, PredecessorMap pred, DistanceMap distance,
  41   BinaryFunction combine, BinaryPredicate compare, BellmanFordVisitor v)
  42 </PRE>
  43
  44 <P>
  45 The Bellman-Ford algorithm&nbsp;[<A
  46 HREF="bibliography.html#bellman58">4</A>,<A
  47 HREF="bibliography.html#ford62:_flows">11</A>,<A
  48 HREF="bibliography.html#lawler76:_comb_opt">20</A>,<A
  49 HREF="bibliography.html#clr90">8</A>] solves the single-source
  50 shortest paths problem for a graph with both positive and negative
  51 edge weights. For the definition of the shortest paths problem see
  52 Section <A
  53 HREF="./graph_theory_review.html#sec:shortest-paths-algorithms">Shortest-Paths
  54 Algorithms</A>.
  55 If you only need to solve the shortest paths problem for positive edge
  56 weights, Dijkstra's algorithm provides a more efficient
  57 alternative. If all the edge weights are all equal to one then breadth-first
  58 search provides an even more efficient alternative.
  59 </p>
  60
  61 <p>
  62 Before calling the <tt>bellman_ford_shortest_paths()</tt> function,
  63 the user must assign the source vertex a distance of zero and all
  64 other vertices a distance of infinity <i>unless</i> you are providing
  65 a starting vertex. The Bellman-Ford algorithm
  66 proceeds by looping through all of the edges in the graph, applying
  67 the relaxation operation to each edge. In the following pseudo-code,
  68 <i>v</i> is a vertex adjacent to <i>u</i>, <i>w</i> maps edges to
  69 their weight, and <i>d</i> is a distance map that records the length
  70 of the shortest path to each vertex seen so far. <i>p</i> is a
  71 predecessor map which records the parent of each vertex, which will
  72 ultimately be the parent in the shortest paths tree
  73 </p>
  74
  75 <table>
  76 <tr>
  77 <td valign="top">
  78 <pre>
  79 RELAX(<i>u</i>, <i>v</i>, <i>w</i>, <i>d</i>, <i>p</i>)
  80   <b>if</b> (<i>w(u,v) + d[u] < d[v]</i>)
  81     <i>d[v] := w(u,v) + d[u]</i>
  82     <i>p[v] := u</i>
  83   <b>else</b>
  84     ...
  85 </pre>
  86 </td>
  87 <td valign="top">
  88 <pre>
  89
  90
  91 relax edge <i>(u,v)</i>
  92
  93
  94 edge <i>(u,v)</i> is not relaxed
  95 </pre>
  96 </td>
  97 </tr>
  98 </table>
  99
 100 <p>
 101 The algorithm repeats this loop <i>|V|</i> times after which it is
 102 guaranteed that the distances to each vertex have been reduced to the
 103 minimum possible unless there is a negative cycle in the graph. If
 104 there is a negative cycle, then there will be edges in the graph that
 105 were not properly minimized. That is, there will be edges <i>(u,v)</i> such
 106 that <i>w(u,v) + d[u] < d[v]</i>.  The algorithm loops over the edges in
 107 the graph one final time to check if all the edges were minimized,
 108 returning <tt>true</tt> if they were and returning <tt>false</tt>
 109 otherwise.
 110 </p>
 111
 112 <table>
 113 <tr>
 114 <td valign="top">
 115 <pre>
 116 BELLMAN-FORD(<i>G</i>)
 117   <i>// Optional initialization</i>
 118   <b>for</b> each vertex <i>u in V</i>
 119     <i>d[u] := infinity</i>
 120     <i>p[u] := u</i>
 121   <b>end for</b>
 122   <b>for</b> <i>i := 1</i> <b>to</b> <i>|V|-1</i>
 123     <b>for</b> each edge <i>(u,v) in E</i>
 124       RELAX(<i>u</i>, <i>v</i>, <i>w</i>, <i>d</i>, <i>p</i>)
 125     <b>end for</b>
 126   <b>end for</b>
 127   <b>for</b> each edge <i>(u,v) in E</i>
 128     <b>if</b> (<i>w(u,v) + d[u] < d[v]</i>)
 129       <b>return</b> (false, , )
 130     <b>else</b>
 131       ...
 132   <b>end for</b>
 133   <b>return</b> (true, <i>p</i>, <i>d</i>)
 134 </pre>
 135 </td>
 136 <td valign="top">
 137 <pre>
 138
 139
 140
 141
 142
 143
 144
 145 examine edge <i>(u,v)</i>
 146
 147
 148
 149
 150
 151 edge <i>(u,v)</i> was not minimized
 152
 153 edge <i>(u,v)</i> was minimized
 154 </pre>
 155 </td>
 156 </tr>
 157 </table>
 158
 159 There are two main options for obtaining output from the
 160 <tt>bellman_ford_shortest_paths()</tt> function. If the user provides
 161 a distance property map through the <tt>distance_map()</tt> parameter
 162 then the shortest distance from the source vertex to every other
 163 vertex in the graph will be recorded in the distance map (provided the
 164 function returns <tt>true</tt>). The second option is recording the
 165 shortest paths tree in the <tt>predecessor_map()</tt>. For each vertex
 166 <i>u in V</i>, <i>p[u]</i> will be the predecessor of <i>u</i> in the
 167 shortest paths tree (unless <i>p[u] = u</i>, in which case <i>u</i> is
 168 either the source vertex or a vertex unreachable from the source).  In
 169 addition to these two options, the user can provide her own
 170 custom-made visitor that can take actions at any of the
 171 algorithm's event points.
 172
 173 <P>
 174
 175 <h3>Parameters</h3>
 176
 177
 178 IN: <tt>EdgeListGraph&amp; g</tt>
 179 <blockquote>
 180   A directed or undirected graph whose type must be a model of
 181   <a href="./EdgeListGraph.html">Edge List Graph</a>. If a root vertex is
 182   provided, then the graph must also model
 183   <a href="./VertexListGraph.html">Vertex List Graph</a>.<br>
 184
 185   <b>Python</b>: The parameter is named <tt>graph</tt>.
 186 </blockquote>
 187
 188 IN: <tt>Size N</tt>
 189 <blockquote>
 190   The number of vertices in the graph. The type <tt>Size</tt> must
 191   be an integer type.<br>
 192   <b>Default:</b> <tt>num_vertices(g)</tt>.<br>
 193
 194   <b>Python</b>: Unsupported parameter.
 195 </blockquote>
 196
 197
 198 <h3>Named Parameters</h3>
 199
 200 IN: <tt>weight_map(WeightMap w)</tt>
 201 <blockquote>
 202   The weight (also know as ``length'' or ``cost'') of each edge in the
 203   graph.  The <tt>WeightMap</tt> type must be a model of <a
 204   href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
 205   Map</a>.  The key type for this property map must be the edge
 206   descriptor of the graph.  The value type for the weight map must be
 207   <i>Addable</i> with the distance map's value type. <br>
 208   <b>Default:</b> <tt>get(edge_weight, g)</tt><br>
 209
 210   <b>Python</b>: Must be an <tt>edge_double_map</tt> for the graph.<br>
 211   <b>Python default</b>: <tt>graph.get_edge_double_map("weight")</tt>
 212 </blockquote>
 213
 214 OUT: <tt>predecessor_map(PredecessorMap p_map)</tt>
 215 <blockquote>
 216   The predecessor map records the edges in the minimum spanning
 217   tree. Upon completion of the algorithm, the edges <i>(p[u],u)</i>
 218   for all <i>u in V</i> are in the minimum spanning tree. If <i>p[u] =
 219   u</i> then <i>u</i> is either the source vertex or a vertex that is
 220   not reachable from the source.  The <tt>PredecessorMap</tt> type
 221   must be a <a
 222   href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
 223   Property Map</a> which key and vertex types the same as the vertex
 224   descriptor type of the graph.<br>
 225   <b>Default:</b> <tt>dummy_property_map</tt><br>
 226
 227   <b>Python</b>: Must be a <tt>vertex_vertex_map</tt> for the graph.<br>
 228 </blockquote>
 229
 230 IN/OUT: <tt>distance_map(DistanceMap d)</tt>
 231 <blockquote>
 232   The shortest path weight from the source vertex to each vertex in
 233   the graph <tt>g</tt> is recorded in this property map.  The type
 234   <tt>DistanceMap</tt> must be a model of <a
 235   href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
 236   Property Map</a>. The key type of the property map must be the
 237   vertex descriptor type of the graph, and the value type of the
 238   distance map must be <a
 239   href="http://www.sgi.com/tech/stl/LessThanComparable.html"> Less
 240   Than Comparable</a>.<br> <b>Default:</b> <tt>get(vertex_distance,
 241   g)</tt><br>
 242   <b>Python</b>: Must be a <tt>vertex_double_map</tt> for the graph.<br>
 243 </blockquote>
 244
 245 IN: <tt>root_vertex(Vertex s)</tt>
 246 <blockquote>
 247   The starting (or "root") vertex from which shortest paths will be
 248   computed. When provided, the distance map need not be initialized
 249   (the algorithm will perform the initialization itself). However, the
 250   graph must model <a href="./VertexListGraph.html">Vertex List
 251   Graph</a> when this parameter is provided.<br>
 252   <b>Default:</b> None; if omitted, the user must initialize the
 253   distance map.
 254 </blockquote>
 255
 256 IN: <tt>visitor(BellmanFordVisitor v)</tt>
 257 <blockquote>
 258   The visitor object, whose type must be a model of
 259   <a href="./BellmanFordVisitor.html">Bellman-Ford Visitor</a>.
 260   The visitor object is passed by value <a
 261   href="#1">[1]</a>.
 262 <br>
 263   <b>Default:</b> <tt>bellman_visitor&lt;null_visitor&gt;</tt><br>
 264
 265   <b>Python</b>: The parameter should be an object that derives from
 266   the <a
 267   href="BellmanFordVisitor.html#python"><tt>BellmanFordVisitor</tt></a> type
 268   of the graph.
 269
 270 </blockquote>
 271
 272 IN: <tt>distance_combine(BinaryFunction combine)</tt>
 273 <blockquote>
 274   This function object replaces the role of addition in the relaxation
 275   step. The first argument type must match the distance map's value
 276   type and the second argument type must match the weight map's value
 277   type.  The result type must be the same as the distance map's value
 278   type.<br>
 279   <b>Default:</b><tt>std::plus&lt;D&gt;</tt>
 280   with <tt>D=typename&nbsp;property_traits&lt;DistanceMap&gt;::value_type</tt>.<br>
 281
 282   <b>Python</b>: Unsupported parameter.
 283 </blockquote>
 284
 285 IN: <tt>distance_compare(BinaryPredicate compare)</tt>
 286 <blockquote>
 287   This function object replaces the role of the less-than operator
 288   that compares distances in the relaxation step. The argument types
 289   must match the distance map's value type.<br>
 290   <b>Default:</b> <tt>std::less&lt;D&gt;</tt>
 291   with <tt>D=typename&nbsp;property_traits&lt;DistanceMap&gt;::value_type</tt>.<br>
 292
 293   <b>Python</b>: Unsupported parameter.
 294 </blockquote>
 295
 296 <P>
 297
 298 <H3>Complexity</H3>
 299
 300 <P>
 301 The time complexity is <i>O(V E)</i>.
 302
 303
 304 <h3>Visitor Event Points</h3>
 305
 306 <ul>
 307 <li><b><tt>vis.examine_edge(e, g)</tt></b>  is invoked on every edge in
 308   the graph <i>|V|</i> times.
 309 <li><b><tt>vis.edge_relaxed(e, g)</tt></b>  is invoked when the distance
 310   label for the target vertex is decreased. The edge <i>(u,v)</i> that
 311   participated in the last relaxation for vertex <i>v</i> is an edge in the
 312   shortest paths tree.
 313 <li><b><tt>vis.edge_not_relaxed(e, g)</tt></b>  is invoked if the distance label
 314   for the target vertex is not decreased.
 315 <li><b><tt>vis.edge_minimized(e, g)</tt></b>  is invoked during the
 316   second stage of the algorithm, during the test of whether each edge
 317   was minimized. If the edge is minimized then this function
 318   is invoked.
 319 <li><b><tt>vis.edge_not_minimized(e, g)</tt></b>  is also invoked during the
 320   second stage of the algorithm, during the test of whether each edge
 321   was minimized.  If the edge was not minimized, this function is
 322   invoked.  This happens when there is a negative cycle in the graph.
 323 </ul>
 324
 325 <H3>Example</H3>
 326
 327 <P>
 328 An example of using the Bellman-Ford algorithm is in <a
 329 href="../example/bellman-example.cpp"><TT>examples/bellman-example.cpp</TT></a>.
 330
 331 <h3>Notes</h3>
 332
 333 <p><a name="1">[1]</a>
 334   Since the visitor parameter is passed by value, if your visitor
 335   contains state then any changes to the state during the algorithm
 336   will be made to a copy of the visitor object, not the visitor object
 337   passed in. Therefore you may want the visitor to hold this state by
 338   pointer or reference.
 339
 340 <br>
 341 <HR>
 342 <TABLE>
 343 <TR valign=top>
 344 <TD nowrap>Copyright &copy; 2000</TD><TD>
 345 <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
 346 </TD></TR></TABLE>
 347
 348 </BODY>
 349 </HTML>