...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

// named parameter versiontemplate <class VertexAndEdgeListGraph, class DistanceMatrix, class VertexID, class Weight, class BinaryPredicate, class BinaryFunction, class Infinity, class DistanceZero> bool johnson_all_pairs_shortest_paths(VertexAndEdgeListGraph& g1, DistanceMatrix& D, VertexID id1, Weight w1, const BinaryPredicate& compare, const BinaryFunction& combine, const Infinity& inf, DistanceZero zero); template <typename Graph, typename DistanceMatrix, typename P, typename T, typename R> bool johnson_all_pairs_shortest_paths(Graph& g, DistanceMatrix& D, const bgl_named_params<P, T, R>& params =all defaults)// non-named parameter versiontemplate <typename Graph, typename DistanceMatrix, typename VertexIndex, typename WeightMap, typename DT> bool johnson_all_pairs_shortest_paths(VertexAndEdgeListGraph& g1, DistanceMatrix& D, VertexIndex i_map, WeightMap w_map, DT zero)

This algorithm finds the shortest distance between every pair of
vertices in the graph. The algorithm returns false if there is a
negative weight cycle in the graph and true otherwise. The distance
between each pair of vertices is stored in the distance matrix
`D`. This is one of the more time intensive graph algorithms,
having a time complexity of *O(V E log V)*.

This algorithm should be used to compute shortest paths between
every pair of vertices for sparse graphs. For dense graphs, use `floyd_warshall_all_pairs_shortest_paths`

.

`boost/graph/johnson_all_pairs_shortest.hpp`

A directed or undirected graph. The graph type must be a model of Vertex List Graph, Edge List Graph, and Incidence Graph.OUT:

The length of the shortest path between each pair of verticesu,vin the graph is stored inD[u][v]. The tuple of types (DistanceMatrix, vertices_size_type, D) must be a model of BasicMatrix whereDis the value type of theDistanceMap. There must be implicit conversions between the value type of the distance matrix and the value type of the weight map.

The weight or "length" of each edge in the graph. The typeUTIL:WeightMapmust 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. The value type of the weight map must support a subtraction operation.

Default:get(edge_weight, g)

This parameter is no longer needed, and will be ignored.IN:

This maps each vertex to an integer in the rangeUTIL:[0, num_vertices(g)). This is necessary for efficient updates of the heap data structure in the internal call to Dijkstra's algorithm. The typeVertexIndexMapmust be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

Default:get(vertex_index, g)Note: if you use this default, make sure your graph has an internalvertex_indexproperty. For example,adjacency_listwithVertexList=listSdoes not have an internalvertex_indexproperty.

This parameter is no longer needed, and will be ignored.IN:

This function is use to compare distances to determine which vertex is closer to the source vertex. TheIN:CompareFunctiontype must be a model of Binary Predicate and have argument types that match the value type of theWeightMapproperty map.

Default:std::less<DT>withDT=typename property_traits<WeightMap>::value_type

This function is used to combine distances to compute the distance of a path. TheIN:CombineFunctiontype must be a model of Binary Function. Both argument types and the return type of the binary function must match the value type of theWeightMapproperty map. This operation is required to act as the sum operation for the weight type; in particular, it must be the inverse of the binary-operator on that type.

Default:std::plus<DT>withDT=typename property_traits<WeightMap>::value_type

This value is used to initialize the distance for each vertex before the start of the algorithm. The typeIN:DTmust be the value type of theWeightMap.

Default:std::numeric_limits::max()

This value is used to initialize the distance for the source vertex before the start of the algorithm. The typeUTIL/OUT:DTmust be the value type of theWeightMap.

Default:0

This is used during the execution of the algorithm to mark the vertices. The vertices start out white and become gray when they are inserted in the queue. They then turn black when they are removed from the queue. At the end of the algorithm, vertices reachable from the source vertex will have been colored black. All other vertices will still be white. The typeColorMapmust be a model of Read/Write Property Map. A vertex descriptor must be usable as the key type of the map, and the value type of the map must be a model of Color Value.

Default:aniterator_property_mapcreated from astd::vectorofdefault_color_typeof sizenum_vertices(g)and using thei_mapfor the index map.

The file `example/johnson-eg.cpp` applies
Johnson's algorithm for all-pairs shortest paths to the example graph
from page 568 of the CLR [8].

Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu) |