1<HTML> 2<!-- 3 Copyright (c) 2002 Rensselaer Polytechnic Institute 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>Floyd-Warshall All Pairs 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<H1><A NAME="sec:floyd-warshall"> 19<TT>floyd_warshall_all_pairs_shortest_paths</TT> 20</H1> 21 22<PRE><em>// Named parameters version</em> 23template <class VertexListGraph, class DistanceMatrix, 24 class P, class T, class R> 25bool floyd_warshall_initialized_all_pairs_shortest_paths( 26 const VertexListGraph& g, DistanceMatrix& d, 27 const bgl_named_params<P, T, R>& params) 28 29template <class VertexAndEdgeListGraph, class DistanceMatrix, 30 class P, class T, class R> 31bool floyd_warshall_all_pairs_shortest_paths( 32 const VertexAndEdgeListGraph& g, DistanceMatrix& d, 33 const bgl_named_params<P, T, R>& params) 34 35<em>// Positional parameter versions</em> 36\begin{verbatim} 37template <typename VertexListGraph, typename DistanceMatrix, 38 typename BinaryPredicate, typename BinaryFunction, 39 typename Infinity, typename Zero> 40bool floyd_warshall_initialized_all_pairs_shortest_paths( 41 const VertexListGraph& g, DistanceMatrix& d, 42 const BinaryPredicate& compare, const BinaryFunction& combine, 43 const Infinity& inf, const Zero& zero) 44 45template <typename VertexAndEdgeListGraph, typename DistanceMatrix, 46 typename WeightMap, typename BinaryPredicate, 47 typename BinaryFunction, typename Infinity, typename Zero> 48bool floyd_warshall_all_pairs_shortest_paths( 49 const VertexAndEdgeListGraph& g, DistanceMatrix& d, 50 const WeightMap& w, const BinaryPredicate& compare, 51 const BinaryFunction& combine, 52 const Infinity& inf, const Zero& zero)</PRE> 53 54<P> 55These algorithms find the shortest distance between every pair of 56vertices in the graph. The algorithms return false if there is a 57negative weight cycle in the graph, true otherwise. The shortest 58distance between each pair of vertices is stored in the distance 59matrix <code>d</code>. The difference between the two algorithms is in 60whether the distance matrix is assumed to be initialized or not, as 61discussed below under the OUT parameter description. 62 63<P>This algorithm should be used to compute shortest paths between 64every pair of vertices for dense graphs. For sparse graphs, use <a 65href="johnson_all_pairs_shortest.html"><code>johnson_all_pairs_shortest_paths</code></a>. 66 67<H3>Where Defined</H3> 68 69<P> 70<a href="../../../boost/graph/floyd_warshall_shortest.hpp"><TT>boost/graph/floyd_warshall_shortest.hpp</TT></a> 71 72<h3>Parameters</h3> 73IN: <code>Graph& g</code> 74<blockquote> 75A directed or undirected graph. The graph must be a model of <a href="VertexListGraph.html">Vertex List Graph</a> for calls to 76<code>floyd_warshall_initialized_all_pairs_shortest_paths</code>, and 77<a href="VertexAndEdgeListGraph.html">Vertex And Edge List Graph</a> for calls to 78<code>floyd_warshall_all_pairs_shortest_paths</code>.<br> 79</blockquote> 80 81OUT: <code>DistanceMatrix& d</code> 82<blockquote> 83The length of the shortest path between each pair of vertices 84<code>u</code>,<code>v</code> are 85stored in the matrix at location <code>D[u][v]</code>. The 86DistanceMatrix must be 87of type <code>{M, I, V}</code> where <code>I</code> is of type 88<code>vertex_descriptor</code> and <code>V</code> is the 89type of the <code>weight_map</code>. The set of types must be a model of 90<a href="BasicMatrix.html">BasicMatrix</a>, with the exceptions that 91it isn't required to 92run in constant time, and it must be mutable. The matrix must be 93properly initialized when it is passed to the function 94<code>floyd_warshall_initialized_all_pairs_shortest_paths</code>. If the 95function <code>floyd_warshall_all_pairs_shortest_paths</code> is used then the 96matrix will be initialized for the user. 97</blockquote> 98 99<h3>Named Parameters</h3> 100 101IN: <code>weight_map(WeightMap w)</code> 102<blockquote> 103The weight of length of each edge in the graph. The <code>WeightMap</code> 104must be a model of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property 105Map</a>. The edge descriptor 106type of the graph needs to be usable as the key type for the weight 107map. The <code>value_type</code> of the weight map must be the type of the 108<code>DistanceMatrix</code>, and must always either be part of the 109graph passed to the function, or passed in as a parameter.<br> 110<b>Default:</b> <code>get(edge_weight, g)</code> 111</blockquote> 112 113IN: <code>distance_compare(CompareFunction cmp)</code> 114<blockquote> 115The function used to compare distances to determine which target 116vertex is closer to the source vertex. The CompareFunction must be a 117model of <code>BinaryPredicate</code>. The argument types must match the 118value type of the <code>WeightMap</code>.<br> 119 120<b>Default:</b> <code>std::less<WM></code>with <code>WM = typename property_traits<WeightMap>::value_type</code> 121</blockquote> 122 123IN: <code>distance_combine(CombineFunction cmb)</code> 124<blockquote> 125The function used to combine distance to compute the distance of a 126path. The CombineFunction must be a model of <code>BinaryFunction</code>. 127The argument types must match the value type of the <code>WeightMap</code>. 128The result type must be the same as the distance value type.<br> 129 130<b>Default:</b> <code>boost::closed_plus<WM></code> with <code>WM = typename property_traits<WeightMap>::value_type</code> 131</blockquote> 132 133IN: <code>distance_inf(WM inf)</code> 134<blockquote> 135The value used to initialize the distance for each vertex before 136starting the algorithm, and to represent the distance between vertices 137for which there is no path. Should be larger than any possible valid 138path length. The argument type must match the value type of the <code> 139WeightMap</code>.<br> 140 141<b>Default:</b> <code>std::numeric_limits<WM>::max()</code> with <code>WM = typename property_traits<WeightMap>::value_type</code> 142</blockquote> 143 144IN: <code>distance_zero(WM zero)</code> 145<blockquote> 146The value used to represent the distance from a vertex to itself, and 147to determine if a value is negative. The argument type must match the 148value type of the <code>WeightMap</code>.<br> 149<b>Default:</b> <code>0</code> 150</blockquote> 151 152<h3>Complexity</h3> 153 154The time complexity is <i>O(V<sup>3</sup>)</i>. 155 156<br> 157<HR> 158<TABLE> 159<TR valign=top> 160<TD nowrap>Copyright © 2002-2004</TD><TD> 161 Lauren Foutz, Rensselaer Polytechnic Institute</td> 162 </tr><tr valign="top"><td></td> 163 <td>Scott Hill, Rensselaer Polytechnic Institute 164</TD></TR></TABLE> 165 166</BODY> 167</HTML> 168
