123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349 |
- <HTML>
- <!--
- Copyright (c) Jeremy Siek 2000
-
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
- -->
- <Head>
- <Title>Bellman Ford Shortest Paths</Title>
- <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
- <IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
- <BR Clear>
- <H1><A NAME="sec:bellman-ford"></A><img src="figs/python.gif" alt="(Python)"/>
- <TT>bellman_ford_shortest_paths</TT>
- </H1>
- <P>
- <PRE>
- <i>// named paramter version</i>
- template <class <a href="./EdgeListGraph.html">EdgeListGraph</a>, class Size, class P, class T, class R>
- bool bellman_ford_shortest_paths(const EdgeListGraph& g, Size N,
- const bgl_named_params<P, T, R>& params = <i>all defaults</i>);
- template <class <a href="./VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a>, class P, class T, class R>
- bool bellman_ford_shortest_paths(const VertexAndEdgeListGraph& g,
- const bgl_named_params<P, T, R>& params = <i>all defaults</i>);
- <i>// non-named parameter version</i>
- template <class <a href="./EdgeListGraph.html">EdgeListGraph</a>, class Size, class WeightMap,
- class PredecessorMap, class DistanceMap,
- class <a href="http://www.boost.org/sgi/stl/BinaryFunction.html">BinaryFunction</a>, class <a href="http://www.boost.org/sgi/stl/BinaryPredicate.html">BinaryPredicate</a>,
- class <a href="./BellmanFordVisitor.html">BellmanFordVisitor</a>>
- bool bellman_ford_shortest_paths(EdgeListGraph& g, Size N,
- WeightMap weight, PredecessorMap pred, DistanceMap distance,
- BinaryFunction combine, BinaryPredicate compare, BellmanFordVisitor v)
- </PRE>
- <P>
- The Bellman-Ford algorithm [<A
- HREF="bibliography.html#bellman58">4</A>,<A
- HREF="bibliography.html#ford62:_flows">11</A>,<A
- HREF="bibliography.html#lawler76:_comb_opt">20</A>,<A
- HREF="bibliography.html#clr90">8</A>] solves the single-source
- shortest paths problem for a graph with both positive and negative
- edge weights. For the definition of the shortest paths problem see
- Section <A
- HREF="./graph_theory_review.html#sec:shortest-paths-algorithms">Shortest-Paths
- Algorithms</A>.
- If you only need to solve the shortest paths problem for positive edge
- weights, Dijkstra's algorithm provides a more efficient
- alternative. If all the edge weights are all equal to one then breadth-first
- search provides an even more efficient alternative.
- </p>
- <p>
- Before calling the <tt>bellman_ford_shortest_paths()</tt> function,
- the user must assign the source vertex a distance of zero and all
- other vertices a distance of infinity <i>unless</i> you are providing
- a starting vertex. The Bellman-Ford algorithm
- proceeds by looping through all of the edges in the graph, applying
- the relaxation operation to each edge. In the following pseudo-code,
- <i>v</i> is a vertex adjacent to <i>u</i>, <i>w</i> maps edges to
- their weight, and <i>d</i> is a distance map that records the length
- of the shortest path to each vertex seen so far. <i>p</i> is a
- predecessor map which records the parent of each vertex, which will
- ultimately be the parent in the shortest paths tree
- </p>
- <table>
- <tr>
- <td valign="top">
- <pre>
- RELAX(<i>u</i>, <i>v</i>, <i>w</i>, <i>d</i>, <i>p</i>)
- <b>if</b> (<i>w(u,v) + d[u] < d[v]</i>)
- <i>d[v] := w(u,v) + d[u]</i>
- <i>p[v] := u</i>
- <b>else</b>
- ...
- </pre>
- </td>
- <td valign="top">
- <pre>
- relax edge <i>(u,v)</i>
- edge <i>(u,v)</i> is not relaxed
- </pre>
- </td>
- </tr>
- </table>
- <p>
- The algorithm repeats this loop <i>|V|</i> times after which it is
- guaranteed that the distances to each vertex have been reduced to the
- minimum possible unless there is a negative cycle in the graph. If
- there is a negative cycle, then there will be edges in the graph that
- were not properly minimized. That is, there will be edges <i>(u,v)</i> such
- that <i>w(u,v) + d[u] < d[v]</i>. The algorithm loops over the edges in
- the graph one final time to check if all the edges were minimized,
- returning <tt>true</tt> if they were and returning <tt>false</tt>
- otherwise.
- </p>
- <table>
- <tr>
- <td valign="top">
- <pre>
- BELLMAN-FORD(<i>G</i>)
- <i>// Optional initialization</i>
- <b>for</b> each vertex <i>u in V</i>
- <i>d[u] := infinity</i>
- <i>p[u] := u</i>
- <b>end for</b>
- <b>for</b> <i>i := 1</i> <b>to</b> <i>|V|-1</i>
- <b>for</b> each edge <i>(u,v) in E</i>
- RELAX(<i>u</i>, <i>v</i>, <i>w</i>, <i>d</i>, <i>p</i>)
- <b>end for</b>
- <b>end for</b>
- <b>for</b> each edge <i>(u,v) in E</i>
- <b>if</b> (<i>w(u,v) + d[u] < d[v]</i>)
- <b>return</b> (false, , )
- <b>else</b>
- ...
- <b>end for</b>
- <b>return</b> (true, <i>p</i>, <i>d</i>)
- </pre>
- </td>
- <td valign="top">
- <pre>
- examine edge <i>(u,v)</i>
- edge <i>(u,v)</i> was not minimized
- edge <i>(u,v)</i> was minimized
- </pre>
- </td>
- </tr>
- </table>
- There are two main options for obtaining output from the
- <tt>bellman_ford_shortest_paths()</tt> function. If the user provides
- a distance property map through the <tt>distance_map()</tt> parameter
- then the shortest distance from the source vertex to every other
- vertex in the graph will be recorded in the distance map (provided the
- function returns <tt>true</tt>). The second option is recording the
- shortest paths tree in the <tt>predecessor_map()</tt>. For each vertex
- <i>u in V</i>, <i>p[u]</i> will be the predecessor of <i>u</i> in the
- shortest paths tree (unless <i>p[u] = u</i>, in which case <i>u</i> is
- either the source vertex or a vertex unreachable from the source). In
- addition to these two options, the user can provide her own
- custom-made visitor that can take actions at any of the
- algorithm's event points.
- <P>
- <h3>Parameters</h3>
- IN: <tt>EdgeListGraph& g</tt>
- <blockquote>
- A directed or undirected graph whose type must be a model of
- <a href="./EdgeListGraph.html">Edge List Graph</a>. If a root vertex is
- provided, then the graph must also model
- <a href="./VertexListGraph.html">Vertex List Graph</a>.<br>
- <b>Python</b>: The parameter is named <tt>graph</tt>.
- </blockquote>
- IN: <tt>Size N</tt>
- <blockquote>
- The number of vertices in the graph. The type <tt>Size</tt> must
- be an integer type.<br>
- <b>Default:</b> <tt>num_vertices(g)</tt>.<br>
- <b>Python</b>: Unsupported parameter.
- </blockquote>
- <h3>Named Parameters</h3>
- IN: <tt>weight_map(WeightMap w)</tt>
- <blockquote>
- The weight (also know as ``length'' or ``cost'') of each edge in the
- graph. The <tt>WeightMap</tt> type must be a model of <a
- href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
- Map</a>. The key type for this property map must be the edge
- descriptor of the graph. The value type for the weight map must be
- <i>Addable</i> with the distance map's value type. <br>
- <b>Default:</b> <tt>get(edge_weight, g)</tt><br>
- <b>Python</b>: Must be an <tt>edge_double_map</tt> for the graph.<br>
- <b>Python default</b>: <tt>graph.get_edge_double_map("weight")</tt>
- </blockquote>
- OUT: <tt>predecessor_map(PredecessorMap p_map)</tt>
- <blockquote>
- The predecessor map records the edges in the minimum spanning
- tree. Upon completion of the algorithm, the edges <i>(p[u],u)</i>
- for all <i>u in V</i> are in the 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
- must be a <a
- href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
- Property Map</a> which key and vertex types the same as the vertex
- descriptor type of the graph.<br>
- <b>Default:</b> <tt>dummy_property_map</tt><br>
- <b>Python</b>: Must be a <tt>vertex_vertex_map</tt> for the graph.<br>
- </blockquote>
- IN/OUT: <tt>distance_map(DistanceMap d)</tt>
- <blockquote>
- The shortest path weight from the source vertex to each vertex in
- the graph <tt>g</tt> is recorded in this property map. The type
- <tt>DistanceMap</tt> must be a model of <a
- href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
- Property Map</a>. The key type of the property map must be the
- vertex descriptor type of the graph, and the value type of the
- distance map must be <a
- href="http://www.boost.org/sgi/stl/LessThanComparable.html"> Less
- Than Comparable</a>.<br> <b>Default:</b> <tt>get(vertex_distance,
- g)</tt><br>
- <b>Python</b>: Must be a <tt>vertex_double_map</tt> for the graph.<br>
- </blockquote>
- IN: <tt>root_vertex(Vertex s)</tt>
- <blockquote>
- The starting (or "root") vertex from which shortest paths will be
- computed. When provided, the distance map need not be initialized
- (the algorithm will perform the initialization itself). However, the
- graph must model <a href="./VertexListGraph.html">Vertex List
- Graph</a> when this parameter is provided.<br>
- <b>Default:</b> None; if omitted, the user must initialize the
- distance map.
- </blockquote>
- IN: <tt>visitor(BellmanFordVisitor v)</tt>
- <blockquote>
- The visitor object, whose type must be a model of
- <a href="./BellmanFordVisitor.html">Bellman-Ford Visitor</a>.
- The visitor object is passed by value <a
- href="#1">[1]</a>.
- <br>
- <b>Default:</b> <tt>bellman_visitor<null_visitor></tt><br>
- <b>Python</b>: The parameter should be an object that derives from
- the <a
- href="BellmanFordVisitor.html#python"><tt>BellmanFordVisitor</tt></a> type
- of the graph.
- </blockquote>
- IN: <tt>distance_combine(BinaryFunction combine)</tt>
- <blockquote>
- This function object replaces the role of addition in the relaxation
- step. The first argument type must match the distance map's value
- type and the second argument type must match the weight map's value
- type. The result type must be the same as the distance map's value
- type.<br>
- <b>Default:</b><tt>std::plus<D></tt>
- with <tt>D=typename property_traits<DistanceMap>::value_type</tt>.<br>
- <b>Python</b>: Unsupported parameter.
- </blockquote>
- IN: <tt>distance_compare(BinaryPredicate compare)</tt>
- <blockquote>
- This function object replaces the role of the less-than operator
- that compares distances in the relaxation step. The argument types
- must match the distance map's value type.<br>
- <b>Default:</b> <tt>std::less<D></tt>
- with <tt>D=typename property_traits<DistanceMap>::value_type</tt>.<br>
- <b>Python</b>: Unsupported parameter.
- </blockquote>
- <P>
- <H3>Complexity</H3>
- <P>
- The time complexity is <i>O(V E)</i>.
- <h3>Visitor Event Points</h3>
- <ul>
- <li><b><tt>vis.examine_edge(e, g)</tt></b> is invoked on every edge in
- the graph <i>|V|</i> times.
- <li><b><tt>vis.edge_relaxed(e, g)</tt></b> is invoked when the distance
- label for the target vertex is decreased. The edge <i>(u,v)</i> that
- participated in the last relaxation for vertex <i>v</i> is an edge in the
- shortest paths tree.
- <li><b><tt>vis.edge_not_relaxed(e, g)</tt></b> is invoked if the distance label
- for the target vertex is not decreased.
- <li><b><tt>vis.edge_minimized(e, g)</tt></b> is invoked during the
- second stage of the algorithm, during the test of whether each edge
- was minimized. If the edge is minimized then this function
- is invoked.
- <li><b><tt>vis.edge_not_minimized(e, g)</tt></b> is also invoked during the
- second stage of the algorithm, during the test of whether each edge
- was minimized. If the edge was not minimized, this function is
- invoked. This happens when there is a negative cycle in the graph.
- </ul>
- <H3>Example</H3>
- <P>
- An example of using the Bellman-Ford algorithm is in <a
- href="../example/bellman-example.cpp"><TT>examples/bellman-example.cpp</TT></a>.
- <h3>Notes</h3>
- <p><a name="1">[1]</a>
- Since the visitor parameter is passed by value, if your visitor
- contains state then any changes to the state during the algorithm
- will be made to a copy of the visitor object, not the visitor object
- passed in. Therefore you may want the visitor to hold this state by
- pointer or reference.
- <br>
- <HR>
- <TABLE>
- <TR valign=top>
- <TD nowrap>Copyright © 2000</TD><TD>
- <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>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|