equal
deleted
inserted
replaced
139 return new DistMap(graph); |
139 return new DistMap(graph); |
140 } |
140 } |
141 |
141 |
142 }; |
142 }; |
143 |
143 |
144 /// \brief BelmannFord algorithm class. |
144 /// \brief %BelmannFord algorithm class. |
145 /// |
145 /// |
146 /// \ingroup flowalgs |
146 /// \ingroup flowalgs |
147 /// This class provides an efficient implementation of \c Belmann-Ford |
147 /// This class provides an efficient implementation of \c Belmann-Ford |
148 /// algorithm. The edge lengths are passed to the algorithm using a |
148 /// 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 |
149 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any |
150 /// kind of length. |
150 /// kind of length. |
151 /// |
151 /// |
152 /// The Belmann-Ford algorithm solves the shortest path from one node |
152 /// The Belmann-Ford algorithm solves the shortest path from one node |
153 /// problem when the edges can have negative length but the graph should |
153 /// problem when the edges can have negative length but the graph should |
154 /// not contain circle with negative sum of length. If we can assume |
154 /// not contain cycles with negative sum of length. If we can assume |
155 /// that all edge is non-negative in the graph then the dijkstra algorithm |
155 /// that all edge is non-negative in the graph then the dijkstra algorithm |
156 /// should be used rather. |
156 /// should be used rather. |
157 /// |
157 /// |
158 /// The complexity of the algorithm is O(n * e). |
158 /// The complexity of the algorithm is O(n * e). |
159 /// |
159 /// |
426 } |
426 } |
427 if (done) return; |
427 if (done) return; |
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 /// \pre init() must be called and at least one node should be added |
433 /// \pre init() must be called and at least one node should be added |
434 /// with addSource() before using this function. If there is |
434 /// with addSource() before using this function. If there is |
435 /// a negative circle in the graph it gives back false. |
435 /// a negative cycles in the graph it gives back false. |
436 /// |
436 /// |
437 /// This method runs the %BelmannFord algorithm from the root node(s) |
437 /// This method runs the %BelmannFord algorithm from the root node(s) |
438 /// in order to compute the shortest path to each node. The algorithm |
438 /// in order to compute the shortest path to each node. The algorithm |
439 /// computes |
439 /// computes |
440 /// - The shortest path tree. |
440 /// - The shortest path tree. |