94 typedef _Graph Graph; |
94 typedef _Graph Graph; |
95 |
95 |
96 /// \brief The type of the map that stores the edge lengths. |
96 /// \brief The type of the map that stores the edge lengths. |
97 /// |
97 /// |
98 /// The type of the map that stores the edge lengths. |
98 /// The type of the map that stores the edge lengths. |
99 /// It must meet the \ref concept::ReadMap "ReadMap" concept. |
99 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
100 typedef _LengthMap LengthMap; |
100 typedef _LengthMap LengthMap; |
101 |
101 |
102 // The type of the length of the edges. |
102 // The type of the length of the edges. |
103 typedef typename _LengthMap::Value Value; |
103 typedef typename _LengthMap::Value Value; |
104 |
104 |
160 } |
160 } |
161 |
161 |
162 /// \brief The type of the matrix map that stores the dists of the nodes. |
162 /// \brief The type of the matrix map that stores the dists of the nodes. |
163 /// |
163 /// |
164 /// The type of the matrix map that stores the dists of the nodes. |
164 /// The type of the matrix map that stores the dists of the nodes. |
165 /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept. |
165 /// It must meet the \ref concepts::WriteMatrixMap "WriteMatrixMap" concept. |
166 /// |
166 /// |
167 typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap; |
167 typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap; |
168 |
168 |
169 /// \brief Instantiates a DistMap. |
169 /// \brief Instantiates a DistMap. |
170 /// |
170 /// |
180 /// \brief %Johnson algorithm class. |
180 /// \brief %Johnson algorithm class. |
181 /// |
181 /// |
182 /// \ingroup flowalgs |
182 /// \ingroup flowalgs |
183 /// This class provides an efficient implementation of \c %Johnson |
183 /// This class provides an efficient implementation of \c %Johnson |
184 /// algorithm. The edge lengths are passed to the algorithm using a |
184 /// algorithm. The edge lengths are passed to the algorithm using a |
185 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any |
185 /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any |
186 /// kind of length. |
186 /// kind of length. |
187 /// |
187 /// |
188 /// The algorithm solves the shortest path problem for each pair |
188 /// The algorithm solves the shortest path problem for each pair |
189 /// of node when the edges can have negative length but the graph should |
189 /// of node when the edges can have negative length but the graph should |
190 /// not contain cycles with negative sum of length. If we can assume |
190 /// not contain cycles with negative sum of length. If we can assume |
195 /// with fibonacci heap \f$ O(n^2\log(n)+ne) \f$. Usually the fibonacci heap |
195 /// with fibonacci heap \f$ O(n^2\log(n)+ne) \f$. Usually the fibonacci heap |
196 /// implementation is slower than either binary heap implementation or the |
196 /// implementation is slower than either binary heap implementation or the |
197 /// Floyd-Warshall algorithm. |
197 /// Floyd-Warshall algorithm. |
198 /// |
198 /// |
199 /// The type of the length is determined by the |
199 /// The type of the length is determined by the |
200 /// \ref concept::ReadMap::Value "Value" of the length map. |
200 /// \ref concepts::ReadMap::Value "Value" of the length map. |
201 /// |
201 /// |
202 /// \param _Graph The graph type the algorithm runs on. The default value |
202 /// \param _Graph The graph type the algorithm runs on. The default value |
203 /// is \ref ListGraph. The value of _Graph is not used directly by |
203 /// is \ref ListGraph. The value of _Graph is not used directly by |
204 /// Johnson, it is only passed to \ref JohnsonDefaultTraits. |
204 /// Johnson, it is only passed to \ref JohnsonDefaultTraits. |
205 /// \param _LengthMap This read-only EdgeMap determines the lengths of the |
205 /// \param _LengthMap This read-only EdgeMap determines the lengths of the |
206 /// edges. It is read once for each edge, so the map may involve in |
206 /// edges. It is read once for each edge, so the map may involve in |
207 /// relatively time consuming process to compute the edge length if |
207 /// relatively time consuming process to compute the edge length if |
208 /// it is necessary. The default map type is \ref |
208 /// it is necessary. The default map type is \ref |
209 /// concept::Graph::EdgeMap "Graph::EdgeMap<int>". The value |
209 /// concepts::Graph::EdgeMap "Graph::EdgeMap<int>". The value |
210 /// of _LengthMap is not used directly by Johnson, it is only passed |
210 /// of _LengthMap is not used directly by Johnson, it is only passed |
211 /// to \ref JohnsonDefaultTraits. \param _Traits Traits class to set |
211 /// to \ref JohnsonDefaultTraits. \param _Traits Traits class to set |
212 /// various data types used by the algorithm. The default traits |
212 /// various data types used by the algorithm. The default traits |
213 /// class is \ref JohnsonDefaultTraits |
213 /// class is \ref JohnsonDefaultTraits |
214 /// "JohnsonDefaultTraits<_Graph,_LengthMap>". See \ref |
214 /// "JohnsonDefaultTraits<_Graph,_LengthMap>". See \ref |