25 |
25 |
26 #include <lemon/list_graph.h> |
26 #include <lemon/list_graph.h> |
27 #include <lemon/graph_utils.h> |
27 #include <lemon/graph_utils.h> |
28 #include <lemon/invalid.h> |
28 #include <lemon/invalid.h> |
29 #include <lemon/error.h> |
29 #include <lemon/error.h> |
|
30 #include <lemon/matrix_maps.h> |
30 #include <lemon/maps.h> |
31 #include <lemon/maps.h> |
31 |
32 |
32 #include <limits> |
33 #include <limits> |
33 |
34 |
34 namespace lemon { |
35 namespace lemon { |
103 /// It defines the infinity type on the given Value type |
104 /// It defines the infinity type on the given Value type |
104 /// and the used operation. |
105 /// and the used operation. |
105 /// \see FloydWarshallDefaultOperationTraits |
106 /// \see FloydWarshallDefaultOperationTraits |
106 typedef FloydWarshallDefaultOperationTraits<Value> OperationTraits; |
107 typedef FloydWarshallDefaultOperationTraits<Value> OperationTraits; |
107 |
108 |
108 /// \brief The type of the map that stores the last edges of the |
109 /// \brief The type of the matrix map that stores the last edges of the |
109 /// shortest paths. |
110 /// shortest paths. |
110 /// |
111 /// |
111 /// The type of the map that stores the last |
112 /// The type of the map that stores the last edges of the shortest paths. |
112 /// edges of the shortest paths. |
|
113 /// It must be a matrix map with \c Graph::Edge value type. |
113 /// It must be a matrix map with \c Graph::Edge value type. |
114 /// |
114 /// |
115 typedef NodeMatrixMap<Graph, typename Graph::Edge> PredMap; |
115 typedef DynamicMatrixMap<Graph, typename Graph::Node, |
|
116 typename Graph::Edge> PredMap; |
116 |
117 |
117 /// \brief Instantiates a PredMap. |
118 /// \brief Instantiates a PredMap. |
118 /// |
119 /// |
119 /// This function instantiates a \ref PredMap. |
120 /// This function instantiates a \ref PredMap. |
120 /// \param G is the graph, to which we would like to define the PredMap. |
121 /// \param G is the graph, to which we would like to define the PredMap. |
124 } |
125 } |
125 |
126 |
126 /// \brief The type of the map that stores the dists of the nodes. |
127 /// \brief The type of the map that stores the dists of the nodes. |
127 /// |
128 /// |
128 /// The type of the map that stores the dists of the nodes. |
129 /// The type of the map that stores the dists of the nodes. |
129 /// It must meet the \ref concept::WriteMap "WriteMap" concept. |
130 /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept. |
130 /// |
131 /// |
131 typedef NodeMatrixMap<Graph, Value> DistMap; |
132 typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap; |
132 |
133 |
133 /// \brief Instantiates a DistMap. |
134 /// \brief Instantiates a DistMap. |
134 /// |
135 /// |
135 /// This function instantiates a \ref DistMap. |
136 /// This function instantiates a \ref DistMap. |
136 /// \param G is the graph, to which we would like to define the |
137 /// \param G is the graph, to which we would like to define the |
146 /// \ingroup flowalgs |
147 /// \ingroup flowalgs |
147 /// This class provides an efficient implementation of \c FloydWarshall |
148 /// This class provides an efficient implementation of \c FloydWarshall |
148 /// algorithm. The edge lengths are passed to the algorithm using a |
149 /// algorithm. The edge lengths are passed to the algorithm using a |
149 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any |
150 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any |
150 /// kind of length. |
151 /// kind of length. |
|
152 /// |
|
153 /// The algorithm solves the shortest path problem for each pairs |
|
154 /// of node when the edges can have negative length but the graph should |
|
155 /// not contain circle with negative sum of length. If we can assume |
|
156 /// that all edge is non-negative in the graph then the dijkstra algorithm |
|
157 /// should be used from each node rather and if the graph is sparse and |
|
158 /// there are negative circles then the johson algorithm. |
|
159 /// |
|
160 /// The complexity of this algorithm is O(n^3 + e). |
151 /// |
161 /// |
152 /// The type of the length is determined by the |
162 /// The type of the length is determined by the |
153 /// \ref concept::ReadMap::Value "Value" of the length map. |
163 /// \ref concept::ReadMap::Value "Value" of the length map. |
154 /// |
164 /// |
155 /// \param _Graph The graph type the algorithm runs on. The default value |
165 /// \param _Graph The graph type the algorithm runs on. The default value |