92 typedef _Graph Graph; |
92 typedef _Graph Graph; |
93 |
93 |
94 /// \brief The type of the map that stores the edge lengths. |
94 /// \brief The type of the map that stores the edge lengths. |
95 /// |
95 /// |
96 /// The type of the map that stores the edge lengths. |
96 /// The type of the map that stores the edge lengths. |
97 /// It must meet the \ref concept::ReadMap "ReadMap" concept. |
97 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
98 typedef _LengthMap LengthMap; |
98 typedef _LengthMap LengthMap; |
99 |
99 |
100 // The type of the length of the edges. |
100 // The type of the length of the edges. |
101 typedef typename _LengthMap::Value Value; |
101 typedef typename _LengthMap::Value Value; |
102 |
102 |
127 } |
127 } |
128 |
128 |
129 /// \brief The type of the map that stores the dists of the nodes. |
129 /// \brief The type of the map that stores the dists of the nodes. |
130 /// |
130 /// |
131 /// The type of the map that stores the dists of the nodes. |
131 /// The type of the map that stores the dists of the nodes. |
132 /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept. |
132 /// It must meet the \ref concepts::WriteMatrixMap "WriteMatrixMap" concept. |
133 /// |
133 /// |
134 typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap; |
134 typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap; |
135 |
135 |
136 /// \brief Instantiates a DistMap. |
136 /// \brief Instantiates a DistMap. |
137 /// |
137 /// |
147 /// \brief %FloydWarshall algorithm class. |
147 /// \brief %FloydWarshall algorithm class. |
148 /// |
148 /// |
149 /// \ingroup flowalgs |
149 /// \ingroup flowalgs |
150 /// This class provides an efficient implementation of \c Floyd-Warshall |
150 /// This class provides an efficient implementation of \c Floyd-Warshall |
151 /// algorithm. The edge lengths are passed to the algorithm using a |
151 /// algorithm. The edge lengths are passed to the algorithm using a |
152 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any |
152 /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any |
153 /// kind of length. |
153 /// kind of length. |
154 /// |
154 /// |
155 /// The algorithm solves the shortest path problem for each pair |
155 /// The algorithm solves the shortest path problem for each pair |
156 /// of node when the edges can have negative length but the graph should |
156 /// of node when the edges can have negative length but the graph should |
157 /// not contain cycles with negative sum of length. If we can assume |
157 /// not contain cycles with negative sum of length. If we can assume |
160 /// there are negative circles then the johnson algorithm. |
160 /// there are negative circles then the johnson algorithm. |
161 /// |
161 /// |
162 /// The complexity of this algorithm is \f$ O(n^3+e) \f$. |
162 /// The complexity of this algorithm is \f$ O(n^3+e) \f$. |
163 /// |
163 /// |
164 /// The type of the length is determined by the |
164 /// The type of the length is determined by the |
165 /// \ref concept::ReadMap::Value "Value" of the length map. |
165 /// \ref concepts::ReadMap::Value "Value" of the length map. |
166 /// |
166 /// |
167 /// \param _Graph The graph type the algorithm runs on. The default value |
167 /// \param _Graph The graph type the algorithm runs on. The default value |
168 /// is \ref ListGraph. The value of _Graph is not used directly by |
168 /// is \ref ListGraph. The value of _Graph is not used directly by |
169 /// FloydWarshall, it is only passed to \ref FloydWarshallDefaultTraits. |
169 /// FloydWarshall, it is only passed to \ref FloydWarshallDefaultTraits. |
170 /// \param _LengthMap This read-only EdgeMap determines the lengths of the |
170 /// \param _LengthMap This read-only EdgeMap determines the lengths of the |
171 /// edges. It is read once for each edge, so the map may involve in |
171 /// edges. It is read once for each edge, so the map may involve in |
172 /// relatively time consuming process to compute the edge length if |
172 /// relatively time consuming process to compute the edge length if |
173 /// it is necessary. The default map type is \ref |
173 /// it is necessary. The default map type is \ref |
174 /// concept::Graph::EdgeMap "Graph::EdgeMap<int>". The value |
174 /// concepts::Graph::EdgeMap "Graph::EdgeMap<int>". The value |
175 /// of _LengthMap is not used directly by FloydWarshall, it is only passed |
175 /// of _LengthMap is not used directly by FloydWarshall, it is only passed |
176 /// to \ref FloydWarshallDefaultTraits. \param _Traits Traits class to set |
176 /// to \ref FloydWarshallDefaultTraits. \param _Traits Traits class to set |
177 /// various data types used by the algorithm. The default traits |
177 /// various data types used by the algorithm. The default traits |
178 /// class is \ref FloydWarshallDefaultTraits |
178 /// class is \ref FloydWarshallDefaultTraits |
179 /// "FloydWarshallDefaultTraits<_Graph,_LengthMap>". See \ref |
179 /// "FloydWarshallDefaultTraits<_Graph,_LengthMap>". See \ref |