///\todo The graph alone may be insufficient for the initialization

     ///\todo The graph alone may be insufficient for the initialization

     static PredMap *createPredMap(const GR &G) 

     static PredMap *createPredMap(const GR &G) 

     {

     {

       return new PredMap(G);

       return new PredMap(G);

     }

     }

     ///The type of the map that stores whether a nodes is processed.

     ///The type of the map that stores whether a nodes is processed.

     ///The type of the map that stores whether a nodes is processed.

     ///The type of the map that stores whether a nodes is processed.

     ///It must meet the \ref concept::WriteMap "WriteMap" concept.

     ///It must meet the \ref concept::WriteMap "WriteMap" concept.

     ///The type of the map that stores the edge lengths.

     ///The type of the map that stores the edge lengths.

     typedef typename TR::LengthMap LengthMap;

     typedef typename TR::LengthMap LengthMap;

     ///\brief The type of the map that stores the last

     ///\brief The type of the map that stores the last

     ///edges of the shortest paths.

     ///edges of the shortest paths.

     typedef typename TR::PredMap PredMap;

     typedef typename TR::PredMap PredMap;

     ///The type of the map indicating if a node is processed.

     ///The type of the map indicating if a node is processed.

     typedef typename TR::ProcessedMap ProcessedMap;

     typedef typename TR::ProcessedMap ProcessedMap;

     ///The type of the map that stores the dists of the nodes.

     ///The type of the map that stores the dists of the nodes.

     typedef typename TR::DistMap DistMap;

     typedef typename TR::DistMap DistMap;

     ///The heap type used by the dijkstra algorithm.

     ///The heap type used by the dijkstra algorithm.

     const LengthMap *length;

     const LengthMap *length;

     ///Pointer to the map of predecessors edges.

     ///Pointer to the map of predecessors edges.

     PredMap *_pred;

     PredMap *_pred;

     ///Indicates if \ref _pred is locally allocated (\c true) or not.

     ///Indicates if \ref _pred is locally allocated (\c true) or not.

     bool local_pred;

     bool local_pred;

     ///Pointer to the map of distances.

     ///Pointer to the map of distances.

     DistMap *_dist;

     DistMap *_dist;

     ///Indicates if \ref _dist is locally allocated (\c true) or not.

     ///Indicates if \ref _dist is locally allocated (\c true) or not.

     bool local_dist;

     bool local_dist;

     ///Pointer to the map of processed status of the nodes.

     ///Pointer to the map of processed status of the nodes.

     ProcessedMap *_processed;

     ProcessedMap *_processed;

     ///Indicates if \ref _processed is locally allocated (\c true) or not.

     ///Indicates if \ref _processed is locally allocated (\c true) or not.

     bool local_processed;

     bool local_processed;

     ///Creates the maps if necessary.

     ///Creates the maps if necessary.

     ///\todo Error if \c G or are \c NULL. What about \c length?

     ///\todo Error if \c G or are \c NULL. What about \c length?

     ///\todo Better memory allocation (instead of new).

     ///\todo Better memory allocation (instead of new).

     void create_maps() 

     void create_maps() 

     {

     {

       if(!_pred) {

       if(!_pred) {

 	local_pred = true;

 	local_pred = true;

 	_pred = Traits::createPredMap(*G);

 	_pred = Traits::createPredMap(*G);

       }

       }

       if(!_dist) {

       if(!_dist) {

 	local_dist = true;

 	local_dist = true;

 	_dist = Traits::createDistMap(*G);

 	_dist = Traits::createDistMap(*G);

       }

       }

       if(!_processed) {

       if(!_processed) {

     ///

     ///

     template <class T>

     template <class T>

     class DefPredMap : public Dijkstra< Graph,

     class DefPredMap : public Dijkstra< Graph,

 					LengthMap,

 					LengthMap,

 					DefPredMapTraits<T> > { };

 					DefPredMapTraits<T> > { };

     template <class T>

     template <class T>

     struct DefDistMapTraits : public Traits {

     struct DefDistMapTraits : public Traits {

       typedef T DistMap;

       typedef T DistMap;

       static DistMap *createDistMap(const Graph &G) 

       static DistMap *createDistMap(const Graph &G) 

     ///\param _G the graph the algorithm will run on.

     ///\param _G the graph the algorithm will run on.

     ///\param _length the length map used by the algorithm.

     ///\param _length the length map used by the algorithm.

     Dijkstra(const Graph& _G, const LengthMap& _length) :

     Dijkstra(const Graph& _G, const LengthMap& _length) :

       G(&_G), length(&_length),

       G(&_G), length(&_length),

       _pred(NULL), local_pred(false),

       _pred(NULL), local_pred(false),

       _dist(NULL), local_dist(false),

       _dist(NULL), local_dist(false),

       _processed(NULL), local_processed(false),

       _processed(NULL), local_processed(false),

       _heap_map(*G,-1),_heap(_heap_map)

       _heap_map(*G,-1),_heap(_heap_map)

     { }

     { }

     ///Destructor.

     ///Destructor.

     ~Dijkstra() 

     ~Dijkstra() 

     {

     {

       if(local_pred) delete _pred;

       if(local_pred) delete _pred;

       if(local_dist) delete _dist;

       if(local_dist) delete _dist;

       if(local_processed) delete _processed;

       if(local_processed) delete _processed;

     }

     }

     ///Sets the length map.

     ///Sets the length map.

       }

       }

       _pred = &m;

       _pred = &m;

       return *this;

       return *this;

     }

     }

     ///Sets the map storing the distances calculated by the algorithm.

     ///Sets the map storing the distances calculated by the algorithm.

     ///Sets the map storing the distances calculated by the algorithm.

     ///Sets the map storing the distances calculated by the algorithm.

     ///If you don't use this function before calling \ref run(),

     ///If you don't use this function before calling \ref run(),

     ///it will allocate one. The destuctor deallocates this

     ///it will allocate one. The destuctor deallocates this

   private:

   private:

     void finalizeNodeData(Node v,Value dst)

     void finalizeNodeData(Node v,Value dst)

     {

     {

       _processed->set(v,true);

       _processed->set(v,true);

       _dist->set(v, dst);

       _dist->set(v, dst);

     }

     }

   public:

   public:

     ///\name Execution control

     ///\name Execution control

     ///The simplest way to execute the algorithm is to use

     ///The simplest way to execute the algorithm is to use

     {

     {

       create_maps();

       create_maps();

       while(!_heap.empty()) _heap.pop();

       while(!_heap.empty()) _heap.pop();

       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {

       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {

 	_pred->set(u,INVALID);

 	_pred->set(u,INVALID);

 	_processed->set(u,false);

 	_processed->set(u,false);

 	_heap_map.set(u,Heap::PRE_HEAP);

 	_heap_map.set(u,Heap::PRE_HEAP);

       }

       }

     }

     }

     ///It checks if the node has already been added to the heap and

     ///It checks if the node has already been added to the heap and

     ///It is pushed to the heap only if either it was not in the heap

     ///It is pushed to the heap only if either it was not in the heap

     ///or the shortest path found till then is longer then \c dst.

     ///or the shortest path found till then is longer then \c dst.

     void addSource(Node s,Value dst=0)

     void addSource(Node s,Value dst=0)

     {

     {

       if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);

       if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);

       else if(_heap[s]<dst) {

       else if(_heap[s]<dst) {

 	_heap.push(s,dst);

 	_heap.push(s,dst);

 	_pred->set(s,INVALID);

 	_pred->set(s,INVALID);

       }

       }

 	Node w=G->target(e); 

 	Node w=G->target(e); 

 	switch(_heap.state(w)) {

 	switch(_heap.state(w)) {

 	case Heap::PRE_HEAP:

 	case Heap::PRE_HEAP:

 	  _heap.push(w,oldvalue+(*length)[e]); 

 	  _heap.push(w,oldvalue+(*length)[e]); 

 	  _pred->set(w,e);

 	  _pred->set(w,e);

 	  break;

 	  break;

 	case Heap::IN_HEAP:

 	case Heap::IN_HEAP:

 	  if ( oldvalue+(*length)[e] < _heap[w] ) {

 	  if ( oldvalue+(*length)[e] < _heap[w] ) {

 	    _heap.decrease(w, oldvalue+(*length)[e]); 

 	    _heap.decrease(w, oldvalue+(*length)[e]); 

 	    _pred->set(w,e);

 	    _pred->set(w,e);

 	  }

 	  }

 	  break;

 	  break;

 	case Heap::POST_HEAP:

 	case Heap::POST_HEAP:

 	  break;

 	  break;

 	}

 	}

     ///Next node to be processed.

     ///Next node to be processed.

     ///

     ///

     ///\return The next node to be processed or INVALID if the priority heap

     ///\return The next node to be processed or INVALID if the priority heap

     /// is empty.

     /// is empty.

     { 

     { 

       return _heap.empty()?_heap.top():INVALID;

       return _heap.empty()?_heap.top():INVALID;

     }

     }

     ///\brief Returns \c false if there are nodes

     ///\brief Returns \c false if there are nodes

     ///Returns a reference to the NodeMap of the edges of the

     ///Returns a reference to the NodeMap of the edges of the

     ///shortest path tree.

     ///shortest path tree.

     ///\pre \ref run() must be called before using this function.

     ///\pre \ref run() must be called before using this function.

     const PredMap &predMap() const { return *_pred;}

     const PredMap &predMap() const { return *_pred;}

     ///Checks if a node is reachable from the root.

     ///Checks if a node is reachable from the root.

     ///Returns \c true if \c v is reachable from the root.

     ///Returns \c true if \c v is reachable from the root.

     ///\warning The source nodes are inditated as unreached.

     ///\warning The source nodes are inditated as unreached.

     ///\pre \ref run() must be called before using this function.

     ///\pre \ref run() must be called before using this function.

   }

   }

 } //END OF NAMESPACE LEMON

 } //END OF NAMESPACE LEMON

 #endif

 #endif