1.1 --- a/lemon/belmann_ford.h	Fri Oct 14 10:53:35 2005 +0000
     1.2 +++ b/lemon/belmann_ford.h	Fri Oct 14 10:53:51 2005 +0000
     1.3 @@ -144,11 +144,19 @@
     1.4    /// \brief BelmannFord algorithm class.
     1.5    ///
     1.6    /// \ingroup flowalgs
     1.7 -  /// This class provides an efficient implementation of \c BelmannFord 
     1.8 +  /// This class provides an efficient implementation of \c Belmann-Ford 
     1.9    /// algorithm. The edge lengths are passed to the algorithm using a
    1.10    /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any 
    1.11    /// kind of length.
    1.12    ///
    1.13 +  /// The Belmann-Ford algorithm solves the shortest path from one node
    1.14 +  /// problem when the edges can have negative length but the graph should
    1.15 +  /// not contain circle with negative sum of length. If we can assume
    1.16 +  /// that all edge is non-negative in the graph then the dijkstra algorithm
    1.17 +  /// should be used rather.
    1.18 +  ///
    1.19 +  /// The complexity of the algorithm is O(n * e).
    1.20 +  ///
    1.21    /// The type of the length is determined by the
    1.22    /// \ref concept::ReadMap::Value "Value" of the length map.
    1.23    ///
    1.24 @@ -402,9 +410,9 @@
    1.25      /// - The shortest path tree.
    1.26      /// - The distance of each node from the root(s).
    1.27      void start() {
    1.28 -      bool ready = false;
    1.29 -      while (!ready) {
    1.30 -	ready = true;
    1.31 +      int num = countNodes(*graph) - 1;
    1.32 +      for (int i = 0; i < num; ++i) {
    1.33 +	bool ready = true;
    1.34  	for (EdgeIt it(*graph); it != INVALID; ++it) {
    1.35  	  Node source = graph->source(it);
    1.36  	  Node target = graph->target(it);
    1.37 @@ -416,8 +424,40 @@
    1.38  	    ready = false; 
    1.39  	  }
    1.40  	}
    1.41 +	if (ready) return;
    1.42        }
    1.43      }
    1.44 +
    1.45 +    /// \brief Executes the algorithm and check the negative circles.
    1.46 +    ///
    1.47 +    /// \pre init() must be called and at least one node should be added
    1.48 +    /// with addSource() before using this function. If there is
    1.49 +    /// a negative circle in the graph it gives back false.
    1.50 +    ///
    1.51 +    /// This method runs the %BelmannFord algorithm from the root node(s)
    1.52 +    /// in order to compute the shortest path to each node. The algorithm 
    1.53 +    /// computes 
    1.54 +    /// - The shortest path tree.
    1.55 +    /// - The distance of each node from the root(s).
    1.56 +    bool checkedStart() {
    1.57 +      int num = countNodes(*graph);
    1.58 +      for (int i = 0; i < num; ++i) {
    1.59 +	bool ready = true;
    1.60 +	for (EdgeIt it(*graph); it != INVALID; ++it) {
    1.61 +	  Node source = graph->source(it);
    1.62 +	  Node target = graph->target(it);
    1.63 +	  Value relaxed = 
    1.64 +	    OperationTraits::plus((*_dist)[source], (*length)[it]);
    1.65 +	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
    1.66 +	    _pred->set(target, it);
    1.67 +	    _dist->set(target, relaxed);
    1.68 +	    ready = false; 
    1.69 +	  }
    1.70 +	}
    1.71 +	if (ready) return true;
    1.72 +      }
    1.73 +      return false;
    1.74 +    }
    1.75      
    1.76      /// \brief Runs %BelmannFord algorithm from node \c s.
    1.77      ///