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