...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
// Named parameters version 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) // Positional parameter versions \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)
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 d
. 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.
This algorithm should be used to compute shortest paths between
every pair of vertices for dense graphs. For sparse graphs, use johnson_all_pairs_shortest_paths
.
boost/graph/floyd_warshall_shortest.hpp
Graph& g
A directed or undirected graph. The graph must be a model of Vertex List Graph for calls toOUT:floyd_warshall_initialized_all_pairs_shortest_paths
, and Vertex And Edge List Graph for calls tofloyd_warshall_all_pairs_shortest_paths
.
DistanceMatrix& d
The length of the shortest path between each pair of verticesu
,v
are stored in the matrix at locationD[u][v]
. The DistanceMatrix must be of type{M, I, V}
whereI
is of typevertex_descriptor
andV
is the type of theweight_map
. The set of types must be a model of BasicMatrix, 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 functionfloyd_warshall_initialized_all_pairs_shortest_paths
. If the functionfloyd_warshall_all_pairs_shortest_paths
is used then the matrix will be initialized for the user.
weight_map(WeightMap w)
The weight of length of each edge in the graph. TheIN:WeightMap
must be a model of Readable Property Map. The edge descriptor type of the graph needs to be usable as the key type for the weight map. Thevalue_type
of the weight map must be the type of theDistanceMatrix
, and must always either be part of the graph passed to the function, or passed in as a parameter.
Default:get(edge_weight, g)
distance_compare(CompareFunction cmp)
The function used to compare distances to determine which target vertex is closer to the source vertex. The CompareFunction must be a model ofIN:BinaryPredicate
. The argument types must match the value type of theWeightMap
.
Default:std::less<WM>
withWM = typename property_traits<WeightMap>::value_type
distance_combine(CombineFunction cmb)
The function used to combine distance to compute the distance of a path. The CombineFunction must be a model ofIN:BinaryFunction
. The argument types must match the value type of theWeightMap
. The result type must be the same as the distance value type.
Default:boost::closed_plus<WM>
withWM = typename property_traits<WeightMap>::value_type
distance_inf(WM inf)
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 theIN:WeightMap
.
Default:std::numeric_limits<WM>::max()
withWM = typename property_traits<WeightMap>::value_type
distance_zero(WM zero)
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 theWeightMap
.
Default:0
Copyright © 2002-2004 | Lauren Foutz, Rensselaer Polytechnic Institute |
Scott Hill, Rensselaer Polytechnic Institute |