140 return new DistMap(graph); |
140 return new DistMap(graph); |
141 } |
141 } |
142 |
142 |
143 }; |
143 }; |
144 |
144 |
145 /// \brief FloydWarshall algorithm class. |
145 /// \brief %FloydWarshall algorithm class. |
146 /// |
146 /// |
147 /// \ingroup flowalgs |
147 /// \ingroup flowalgs |
148 /// This class provides an efficient implementation of \c FloydWarshall |
148 /// This class provides an efficient implementation of \c Floyd-Warshall |
149 /// algorithm. The edge lengths are passed to the algorithm using a |
149 /// 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 |
150 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any |
151 /// kind of length. |
151 /// kind of length. |
152 /// |
152 /// |
153 /// The algorithm solves the shortest path problem for each pairs |
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 |
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 |
155 /// not contain cycles with negative sum of length. If we can assume |
156 /// that all edge is non-negative in the graph then the dijkstra algorithm |
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 |
157 /// should be used from each node rather and if the graph is sparse and |
158 /// there are negative circles then the johson algorithm. |
158 /// there are negative circles then the johnson algorithm. |
159 /// |
159 /// |
160 /// The complexity of this algorithm is O(n^3 + e). |
160 /// The complexity of this algorithm is O(n^3 + e). |
161 /// |
161 /// |
162 /// The type of the length is determined by the |
162 /// The type of the length is determined by the |
163 /// \ref concept::ReadMap::Value "Value" of the length map. |
163 /// \ref concept::ReadMap::Value "Value" of the length map. |
426 } |
426 } |
427 } |
427 } |
428 } |
428 } |
429 } |
429 } |
430 |
430 |
431 /// \brief Executes the algorithm and checks the negative circles. |
431 /// \brief Executes the algorithm and checks the negative cycles. |
432 /// |
432 /// |
433 /// This method runs the %FloydWarshall algorithm in order to compute |
433 /// This method runs the %FloydWarshall algorithm in order to compute |
434 /// the shortest path to each node pairs. If there is a negative circle |
434 /// the shortest path to each node pairs. If there is a negative cycle |
435 /// in the graph it gives back false. |
435 /// in the graph it gives back false. |
436 /// The algorithm computes |
436 /// The algorithm computes |
437 /// - The shortest path tree for each node. |
437 /// - The shortest path tree for each node. |
438 /// - The distance between each node pairs. |
438 /// - The distance between each node pairs. |
439 bool checkedStart() { |
439 bool checkedStart() { |