123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167 |
- <HTML>
- <!--
- Copyright (c) 2002 Rensselaer Polytechnic Institute
-
- 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>Floyd-Warshall All Pairs 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:floyd-warshall">
- <TT>floyd_warshall_all_pairs_shortest_paths</TT>
- </H1>
- <PRE><em>// Named parameters version</em>
- template <class VertexListGraph, class DistanceMatrix,
- class P, class T, class R>
- bool floyd_warshall_initialized_all_pairs_shortest_paths(
- const VertexListGraph& g, DistanceMatrix& d,
- const bgl_named_params<P, T, R>& params)
- template <class VertexAndEdgeListGraph, class DistanceMatrix,
- class P, class T, class R>
- bool floyd_warshall_all_pairs_shortest_paths(
- const VertexAndEdgeListGraph& g, DistanceMatrix& d,
- const bgl_named_params<P, T, R>& params)
- <em>// Positional parameter versions</em>
- \begin{verbatim}
- template <typename VertexListGraph, typename DistanceMatrix,
- typename BinaryPredicate, typename BinaryFunction,
- typename Infinity, typename Zero>
- bool floyd_warshall_initialized_all_pairs_shortest_paths(
- const VertexListGraph& g, DistanceMatrix& d,
- const BinaryPredicate& compare, const BinaryFunction& combine,
- const Infinity& inf, const Zero& zero)
- template <typename VertexAndEdgeListGraph, typename DistanceMatrix,
- typename WeightMap, typename BinaryPredicate,
- typename BinaryFunction, typename Infinity, typename Zero>
- bool floyd_warshall_all_pairs_shortest_paths(
- const VertexAndEdgeListGraph& g, DistanceMatrix& d,
- const WeightMap& w, const BinaryPredicate& compare,
- const BinaryFunction& combine,
- const Infinity& inf, const Zero& zero)</PRE>
- <P>
- These algorithms find the shortest distance between every pair of
- vertices in the graph. The algorithms return false if there is a
- negative weight cycle in the graph, true otherwise. The shortest
- distance between each pair of vertices is stored in the distance
- matrix <code>d</code>. The difference between the two algorithms is in
- whether the distance matrix is assumed to be initialized or not, as
- discussed below under the OUT parameter description.
- <P>This algorithm should be used to compute shortest paths between
- every pair of vertices for dense graphs. For sparse graphs, use <a
- href="johnson_all_pairs_shortest.html"><code>johnson_all_pairs_shortest_paths</code></a>.
- <H3>Where Defined</H3>
- <P>
- <a href="../../../boost/graph/floyd_warshall_shortest.hpp"><TT>boost/graph/floyd_warshall_shortest.hpp</TT></a>
- <h3>Parameters</h3>
- IN: <code>Graph& g</code>
- <blockquote>
- A directed or undirected graph. The graph must be a model of <a href="VertexListGraph.html">Vertex List Graph</a> for calls to
- <code>floyd_warshall_initialized_all_pairs_shortest_paths</code>, and
- <a href="VertexAndEdgeListGraph.html">Vertex And Edge List Graph</a> for calls to
- <code>floyd_warshall_all_pairs_shortest_paths</code>.<br>
- </blockquote>
- OUT: <code>DistanceMatrix& d</code>
- <blockquote>
- The length of the shortest path between each pair of vertices
- <code>u</code>,<code>v</code> are
- stored in the matrix at location <code>D[u][v]</code>. The
- DistanceMatrix must be
- of type <code>{M, I, V}</code> where <code>I</code> is of type
- <code>vertex_descriptor</code> and <code>V</code> is the
- type of the <code>weight_map</code>. The set of types must be a model of
- <a href="BasicMatrix.html">BasicMatrix</a>, with the exceptions that
- it isn't required to
- run in constant time, and it must be mutable. The matrix must be
- properly initialized when it is passed to the function
- <code>floyd_warshall_initialized_all_pairs_shortest_paths</code>. If the
- function <code>floyd_warshall_all_pairs_shortest_paths</code> is used then the
- matrix will be initialized for the user.
- </blockquote>
- <h3>Named Parameters</h3>
- IN: <code>weight_map(WeightMap w)</code>
- <blockquote>
- The weight of length of each edge in the graph. The <code>WeightMap</code>
- must be a model of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
- Map</a>. The edge descriptor
- type of the graph needs to be usable as the key type for the weight
- map. The <code>value_type</code> of the weight map must be the type of the
- <code>DistanceMatrix</code>, and must always either be part of the
- graph passed to the function, or passed in as a parameter.<br>
- <b>Default:</b> <code>get(edge_weight, g)</code>
- </blockquote>
- IN: <code>distance_compare(CompareFunction cmp)</code>
- <blockquote>
- The function used to compare distances to determine which target
- vertex is closer to the source vertex. The CompareFunction must be a
- model of <code>BinaryPredicate</code>. The argument types must match the
- value type of the <code>WeightMap</code>.<br>
- <b>Default:</b> <code>std::less<WM></code>with <code>WM = typename property_traits<WeightMap>::value_type</code>
- </blockquote>
- IN: <code>distance_combine(CombineFunction cmb)</code>
- <blockquote>
- The function used to combine distance to compute the distance of a
- path. The CombineFunction must be a model of <code>BinaryFunction</code>.
- The argument types must match the value type of the <code>WeightMap</code>.
- The result type must be the same as the distance value type.<br>
- <b>Default:</b> <code>boost::closed_plus<WM></code> with <code>WM = typename property_traits<WeightMap>::value_type</code>
- </blockquote>
- IN: <code>distance_inf(WM inf)</code>
- <blockquote>
- The value used to initialize the distance for each vertex before
- starting the algorithm, and to represent the distance between vertices
- for which there is no path. Should be larger than any possible valid
- path length. The argument type must match the value type of the <code>
- WeightMap</code>.<br>
- <b>Default:</b> <code>std::numeric_limits<WM>::max()</code> with <code>WM = typename property_traits<WeightMap>::value_type</code>
- </blockquote>
- IN: <code>distance_zero(WM zero)</code>
- <blockquote>
- The value used to represent the distance from a vertex to itself, and
- to determine if a value is negative. The argument type must match the
- value type of the <code>WeightMap</code>.<br>
- <b>Default:</b> <code>0</code>
- </blockquote>
- <h3>Complexity</h3>
- The time complexity is <i>O(V<sup>3</sup>)</i>.
- <br>
- <HR>
- <TABLE>
- <TR valign=top>
- <TD nowrap>Copyright © 2002-2004</TD><TD>
- Lauren Foutz, Rensselaer Polytechnic Institute</td>
- </tr><tr valign="top"><td></td>
- <td>Scott Hill, Rensselaer Polytechnic Institute
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|