1.1 --- a/lemon/dijkstra.h	Tue Sep 23 18:42:49 2008 +0200
     1.2 +++ b/lemon/dijkstra.h	Fri Sep 26 12:40:11 2008 +0200
     1.3 @@ -728,23 +728,26 @@
     1.4        while ( !emptyQueue() ) processNextNode();
     1.5      }
     1.6  
     1.7 -    ///Executes the algorithm until the given target node is reached.
     1.8 +    ///Executes the algorithm until the given target node is processed.
     1.9  
    1.10 -    ///Executes the algorithm until the given target node is reached.
    1.11 +    ///Executes the algorithm until the given target node is processed.
    1.12      ///
    1.13      ///This method runs the %Dijkstra algorithm from the root node(s)
    1.14 -    ///in order to compute the shortest path to \c dest.
    1.15 +    ///in order to compute the shortest path to \c t.
    1.16      ///
    1.17      ///The algorithm computes
    1.18 -    ///- the shortest path to \c dest,
    1.19 -    ///- the distance of \c dest from the root(s).
    1.20 +    ///- the shortest path to \c t,
    1.21 +    ///- the distance of \c t from the root(s).
    1.22      ///
    1.23      ///\pre init() must be called and at least one root node should be
    1.24      ///added with addSource() before using this function.
    1.25 -    void start(Node dest)
    1.26 +    void start(Node t)
    1.27      {
    1.28 -      while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
    1.29 -      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
    1.30 +      while ( !_heap->empty() && _heap->top()!=t ) processNextNode();
    1.31 +      if ( !_heap->empty() ) {
    1.32 +        finalizeNodeData(_heap->top(),_heap->prio());
    1.33 +        _heap->pop();
    1.34 +      }
    1.35      }
    1.36  
    1.37      ///Executes the algorithm until a condition is met.
    1.38 @@ -772,7 +775,7 @@
    1.39        return _heap->top();
    1.40      }
    1.41  
    1.42 -    ///Runs the algorithm from the given node.
    1.43 +    ///Runs the algorithm from the given source node.
    1.44  
    1.45      ///This method runs the %Dijkstra algorithm from node \c s
    1.46      ///in order to compute the shortest path to each node.
    1.47 @@ -796,10 +799,10 @@
    1.48      ///Finds the shortest path between \c s and \c t.
    1.49  
    1.50      ///This method runs the %Dijkstra algorithm from node \c s
    1.51 -    ///in order to compute the shortest path to \c t.
    1.52 +    ///in order to compute the shortest path to node \c t
    1.53 +    ///(it stops searching when \c t is processed).
    1.54      ///
    1.55 -    ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
    1.56 -    ///if \c t is reachable form \c s, \c 0 otherwise.
    1.57 +    ///\return \c true if \c t is reachable form \c s.
    1.58      ///
    1.59      ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
    1.60      ///shortcut of the following code.
    1.61 @@ -808,11 +811,11 @@
    1.62      ///  d.addSource(s);
    1.63      ///  d.start(t);
    1.64      ///\endcode
    1.65 -    Value run(Node s,Node t) {
    1.66 +    bool run(Node s,Node t) {
    1.67        init();
    1.68        addSource(s);
    1.69        start(t);
    1.70 -      return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
    1.71 +      return (*_heap_cross_ref)[t] == Heap::POST_HEAP;
    1.72      }
    1.73  
    1.74      ///@}
    1.75 @@ -908,7 +911,7 @@
    1.76  
    1.77      ///Returns \c true if \c v is processed, i.e. the shortest
    1.78      ///path to \c v has already found.
    1.79 -    ///\pre Either \ref run() or \ref start()
    1.80 +    ///\pre Either \ref run() or \ref init()
    1.81      ///must be called before using this function.
    1.82      bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
    1.83                                            Heap::POST_HEAP; }
    1.84 @@ -917,8 +920,12 @@
    1.85  
    1.86      ///Returns the current distance of a node from the root(s).
    1.87      ///It may be decreased in the following processes.
    1.88 -    ///\pre \c v should be reached but not processed.
    1.89 -    Value currentDist(Node v) const { return (*_heap)[v]; }
    1.90 +    ///\pre Either \ref run() or \ref init()
    1.91 +    ///must be called before using this function and
    1.92 +    ///node \c v must be reached but not necessarily processed.
    1.93 +    Value currentDist(Node v) const {
    1.94 +      return processed(v) ? (*_dist)[v] : (*_heap)[v];
    1.95 +    }
    1.96  
    1.97      ///@}
    1.98    };