[ceph.git] / ceph / src / boost / libs / graph / doc / bellman_ford_shortest.html

<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 &lt;class <a href="./EdgeListGraph.html">EdgeListGraph</a>, class Size, class P, class T, class R&gt;
bool bellman_ford_shortest_paths(const EdgeListGraph&amp; g, Size N, 
  const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>);

template &lt;class <a href="./VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a>, class P, class T, class R&gt;
bool bellman_ford_shortest_paths(const VertexAndEdgeListGraph&amp; g,
  const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>);

<i>// non-named parameter version</i>
template &lt;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>&gt;
bool bellman_ford_shortest_paths(EdgeListGraph&amp; g, Size N, 
  WeightMap weight, PredecessorMap pred, DistanceMap distance, 
  BinaryFunction combine, BinaryPredicate compare, BellmanFordVisitor v)
</PRE>

<P>
The Bellman-Ford algorithm&nbsp;[<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&amp; 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&lt;null_visitor&gt;</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&lt;D&gt;</tt>
  with <tt>D=typename&nbsp;property_traits&lt;DistanceMap&gt;::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&lt;D&gt;</tt>
  with <tt>D=typename&nbsp;property_traits&lt;DistanceMap&gt;::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 &copy; 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>
Commit	Line	Data
7c673cae FG	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 <class <a href="./EdgeListGraph.html">EdgeListGraph</a>, class Size, class P, class T, class R>
	27	bool bellman_ford_shortest_paths(const EdgeListGraph& g, Size N,
	28	const bgl_named_params<P, T, R>& params = <i>all defaults</i>);
	29
	30	template <class <a href="./VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a>, class P, class T, class R>
	31	bool bellman_ford_shortest_paths(const VertexAndEdgeListGraph& g,
	32	const bgl_named_params<P, T, R>& params = <i>all defaults</i>);
	33
	34	<i>// non-named parameter version</i>
	35	template <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>>
	39	bool bellman_ford_shortest_paths(EdgeListGraph& 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 [<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& 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<null_visitor></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<D></tt>
280	with <tt>D=typename property_traits<DistanceMap>::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<D></tt>
291	with <tt>D=typename property_traits<DistanceMap>::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 © 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>