- Better addSource()
authoralpar
Fri, 18 Feb 2005 14:46:04 +0000
changeset 1155fe0fcdb5687b
parent 1154 f07c1c442e6c
child 1156 91f9236dfec9
- Better addSource()
- More docs
src/lemon/dijkstra.h
     1.1 --- a/src/lemon/dijkstra.h	Fri Feb 18 10:36:13 2005 +0000
     1.2 +++ b/src/lemon/dijkstra.h	Fri Feb 18 14:46:04 2005 +0000
     1.3 @@ -483,18 +483,28 @@
     1.4      
     1.5      ///Adds a new source node.
     1.6  
     1.7 -    ///Adds a new source node the the priority heap.
     1.8 -    ///It checks if the node has already been added to the heap.
     1.9 +    ///Adds a new source node to the priority heap.
    1.10      ///
    1.11      ///The optional second parameter is the initial distance of the node.
    1.12      ///
    1.13 -    ///\todo Do we really want to check it?
    1.14 +    ///It checks if the node has already been added to the heap and
    1.15 +    ///It is pushed to the heap only if either it was not in the heap
    1.16 +    ///or the shortest path found till then is longer then \c dst.
    1.17      void addSource(Node s,Value dst=0)
    1.18      {
    1.19        source = s;
    1.20        if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
    1.21 +      else if(_heap[s]<dst) {
    1.22 +	_heap.push(s,dst);
    1.23 +	_pred->set(s,INVALID);
    1.24 +      }
    1.25      }
    1.26      
    1.27 +    ///Processes the next node in the priority heap
    1.28 +
    1.29 +    ///Processes the next node in the priority heap.
    1.30 +    ///
    1.31 +    ///\warning The priority heap must not be empty!
    1.32      void processNextNode()
    1.33      {
    1.34        Node v=_heap.top(); 
    1.35 @@ -523,6 +533,17 @@
    1.36        }
    1.37      }
    1.38  
    1.39 +    ///Returns \c false if there are nodes to be processed in the priority heap
    1.40 +
    1.41 +    ///Returns \c false if there are nodes to be processed in the priority heap
    1.42 +    ///
    1.43 +    bool emptyHeap() { return heap.empty(); }
    1.44 +    ///Returns the number of the nodes to be processed in the priority heap
    1.45 +
    1.46 +    ///Returns the number of the nodes to be processed in the priority heap
    1.47 +    ///
    1.48 +    int heapSize() { return heap.size(); }
    1.49 +    
    1.50      ///Executes the algorithm.
    1.51  
    1.52      ///Executes the algorithm.