diff -r 2acb5f9bfa72 -r fb4f801dd692 lemon/belmann_ford.h --- a/lemon/belmann_ford.h Fri Oct 14 10:53:35 2005 +0000 +++ b/lemon/belmann_ford.h Fri Oct 14 10:53:51 2005 +0000 @@ -144,11 +144,19 @@ /// \brief BelmannFord algorithm class. /// /// \ingroup flowalgs - /// This class provides an efficient implementation of \c BelmannFord + /// This class provides an efficient implementation of \c Belmann-Ford /// algorithm. The edge lengths are passed to the algorithm using a /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any /// kind of length. /// + /// The Belmann-Ford algorithm solves the shortest path from one node + /// problem when the edges can have negative length but the graph should + /// not contain circle with negative sum of length. If we can assume + /// that all edge is non-negative in the graph then the dijkstra algorithm + /// should be used rather. + /// + /// The complexity of the algorithm is O(n * e). + /// /// The type of the length is determined by the /// \ref concept::ReadMap::Value "Value" of the length map. /// @@ -402,9 +410,9 @@ /// - The shortest path tree. /// - The distance of each node from the root(s). void start() { - bool ready = false; - while (!ready) { - ready = true; + int num = countNodes(*graph) - 1; + for (int i = 0; i < num; ++i) { + bool ready = true; for (EdgeIt it(*graph); it != INVALID; ++it) { Node source = graph->source(it); Node target = graph->target(it); @@ -416,8 +424,40 @@ ready = false; } } + if (ready) return; } } + + /// \brief Executes the algorithm and check the negative circles. + /// + /// \pre init() must be called and at least one node should be added + /// with addSource() before using this function. If there is + /// a negative circle in the graph it gives back false. + /// + /// This method runs the %BelmannFord algorithm from the root node(s) + /// in order to compute the shortest path to each node. The algorithm + /// computes + /// - The shortest path tree. + /// - The distance of each node from the root(s). + bool checkedStart() { + int num = countNodes(*graph); + for (int i = 0; i < num; ++i) { + bool ready = true; + for (EdgeIt it(*graph); it != INVALID; ++it) { + Node source = graph->source(it); + Node target = graph->target(it); + Value relaxed = + OperationTraits::plus((*_dist)[source], (*length)[it]); + if (OperationTraits::less(relaxed, (*_dist)[target])) { + _pred->set(target, it); + _dist->set(target, relaxed); + ready = false; + } + } + if (ready) return true; + } + return false; + } /// \brief Runs %BelmannFord algorithm from node \c s. ///