| <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 not 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> |