| <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.sgi.com/tech/stl/BinaryFunction.html">BinaryFunction</a>, class <a href="http://www.sgi.com/tech/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.sgi.com/tech/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> |