- dijkstraZero() added. (Until we conclude how to handle the related problem.)
authoralpar
Mon, 24 Oct 2005 08:09:59 +0000
changeset 17342fb5ceac10e7
parent 1733 5e0d97823ba2
child 1735 41e96cd91d6d
- dijkstraZero() added. (Until we conclude how to handle the related problem.)
- processed() query function added.
lemon/dijkstra.h
     1.1 --- a/lemon/dijkstra.h	Fri Oct 21 13:32:12 2005 +0000
     1.2 +++ b/lemon/dijkstra.h	Mon Oct 24 08:09:59 2005 +0000
     1.3 @@ -22,6 +22,7 @@
     1.4  ///\brief Dijkstra algorithm.
     1.5  ///
     1.6  ///\todo getPath() should be implemented! (also for BFS and DFS)
     1.7 +///\todo dijkstraZero() solution should be revised.
     1.8  
     1.9  #include <lemon/list_graph.h>
    1.10  #include <lemon/bin_heap.h>
    1.11 @@ -31,7 +32,7 @@
    1.12  
    1.13  namespace lemon {
    1.14  
    1.15 -
    1.16 +  template<class T> T dijkstraZero() {return 0;}
    1.17    
    1.18    ///Default traits class of Dijkstra class.
    1.19  
    1.20 @@ -499,7 +500,7 @@
    1.21      ///It checks if the node has already been added to the heap and
    1.22      ///It is pushed to the heap only if either it was not in the heap
    1.23      ///or the shortest path found till then is longer then \c dst.
    1.24 -    void addSource(Node s,Value dst=0)
    1.25 +    void addSource(Node s,Value dst=dijkstraZero<Value>())
    1.26      {
    1.27        if(_heap->state(s) != Heap::IN_HEAP) {
    1.28  	_heap->push(s,dst);
    1.29 @@ -659,7 +660,7 @@
    1.30        init();
    1.31        addSource(s);
    1.32        start(t);
    1.33 -      return (*_pred)[t]==INVALID?0:(*_dist)[t];
    1.34 +      return (*_pred)[t]==INVALID?dijkstraZero<Value>():(*_dist)[t];
    1.35      }
    1.36      
    1.37      ///@}
    1.38 @@ -746,6 +747,14 @@
    1.39      ///\pre \ref run() must be called before using this function.
    1.40      ///
    1.41      bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
    1.42 +
    1.43 +    ///Checks if a node is processed.
    1.44 +
    1.45 +    ///Returns \c true if \c v is processed, i.e. the shortest
    1.46 +    ///path to \c v has already found.
    1.47 +    ///\pre \ref run() must be called before using this function.
    1.48 +    ///
    1.49 +    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
    1.50      
    1.51      ///@}
    1.52    };