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 BelmannFord |
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 /// |
|
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 |
|
154 /// not contain circle with negative sum of length. If we can assume |
|
155 /// that all edge is non-negative in the graph then the dijkstra algorithm |
|
156 /// should be used rather. |
|
157 /// |
|
158 /// The complexity of the algorithm is O(n * e). |
151 /// |
159 /// |
152 /// The type of the length is determined by the |
160 /// The type of the length is determined by the |
153 /// \ref concept::ReadMap::Value "Value" of the length map. |
161 /// \ref concept::ReadMap::Value "Value" of the length map. |
154 /// |
162 /// |
155 /// \param _Graph The graph type the algorithm runs on. The default value |
163 /// \param _Graph The graph type the algorithm runs on. The default value |
400 /// in order to compute the shortest path to each node. The algorithm |
408 /// in order to compute the shortest path to each node. The algorithm |
401 /// computes |
409 /// computes |
402 /// - The shortest path tree. |
410 /// - The shortest path tree. |
403 /// - The distance of each node from the root(s). |
411 /// - The distance of each node from the root(s). |
404 void start() { |
412 void start() { |
405 bool ready = false; |
413 int num = countNodes(*graph) - 1; |
406 while (!ready) { |
414 for (int i = 0; i < num; ++i) { |
407 ready = true; |
415 bool ready = true; |
408 for (EdgeIt it(*graph); it != INVALID; ++it) { |
416 for (EdgeIt it(*graph); it != INVALID; ++it) { |
409 Node source = graph->source(it); |
417 Node source = graph->source(it); |
410 Node target = graph->target(it); |
418 Node target = graph->target(it); |
411 Value relaxed = |
419 Value relaxed = |
412 OperationTraits::plus((*_dist)[source], (*length)[it]); |
420 OperationTraits::plus((*_dist)[source], (*length)[it]); |
414 _pred->set(target, it); |
422 _pred->set(target, it); |
415 _dist->set(target, relaxed); |
423 _dist->set(target, relaxed); |
416 ready = false; |
424 ready = false; |
417 } |
425 } |
418 } |
426 } |
419 } |
427 if (ready) return; |
|
428 } |
|
429 } |
|
430 |
|
431 /// \brief Executes the algorithm and check the negative circles. |
|
432 /// |
|
433 /// \pre init() must be called and at least one node should be added |
|
434 /// with addSource() before using this function. If there is |
|
435 /// a negative circle in the graph it gives back false. |
|
436 /// |
|
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 |
|
439 /// computes |
|
440 /// - The shortest path tree. |
|
441 /// - The distance of each node from the root(s). |
|
442 bool checkedStart() { |
|
443 int num = countNodes(*graph); |
|
444 for (int i = 0; i < num; ++i) { |
|
445 bool ready = true; |
|
446 for (EdgeIt it(*graph); it != INVALID; ++it) { |
|
447 Node source = graph->source(it); |
|
448 Node target = graph->target(it); |
|
449 Value relaxed = |
|
450 OperationTraits::plus((*_dist)[source], (*length)[it]); |
|
451 if (OperationTraits::less(relaxed, (*_dist)[target])) { |
|
452 _pred->set(target, it); |
|
453 _dist->set(target, relaxed); |
|
454 ready = false; |
|
455 } |
|
456 } |
|
457 if (ready) return true; |
|
458 } |
|
459 return false; |
420 } |
460 } |
421 |
461 |
422 /// \brief Runs %BelmannFord algorithm from node \c s. |
462 /// \brief Runs %BelmannFord algorithm from node \c s. |
423 /// |
463 /// |
424 /// This method runs the %BelmannFord algorithm from a root node \c s |
464 /// This method runs the %BelmannFord algorithm from a root node \c s |