lemon/dijkstra.h
changeset 452 aea2dc0518ce
parent 397 62f9787c516c
parent 405 6b9057cdcd8b
child 440 88ed40ad0d4f
equal deleted inserted replaced
20:90e56769e5c9 22:0a499103dbaa
   177   ///There is also a \ref dijkstra() "function-type interface" for the
   177   ///There is also a \ref dijkstra() "function-type interface" for the
   178   ///%Dijkstra algorithm, which is convenient in the simplier cases and
   178   ///%Dijkstra algorithm, which is convenient in the simplier cases and
   179   ///it can be used easier.
   179   ///it can be used easier.
   180   ///
   180   ///
   181   ///\tparam GR The type of the digraph the algorithm runs on.
   181   ///\tparam GR The type of the digraph the algorithm runs on.
   182   ///The default value is \ref ListDigraph.
   182   ///The default type is \ref ListDigraph.
   183   ///The value of GR is not used directly by \ref Dijkstra, it is only
   183   ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies
   184   ///passed to \ref DijkstraDefaultTraits.
   184   ///the lengths of the arcs.
   185   ///\tparam LM A readable arc map that determines the lengths of the
   185   ///It is read once for each arc, so the map may involve in
   186   ///arcs. It is read once for each arc, so the map may involve in
       
   187   ///relatively time consuming process to compute the arc lengths if
   186   ///relatively time consuming process to compute the arc lengths if
   188   ///it is necessary. The default map type is \ref
   187   ///it is necessary. The default map type is \ref
   189   ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
   188   ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
   190   ///The value of LM is not used directly by \ref Dijkstra, it is only
       
   191   ///passed to \ref DijkstraDefaultTraits.
       
   192   ///\tparam TR Traits class to set various data types used by the algorithm.
       
   193   ///The default traits class is \ref DijkstraDefaultTraits
       
   194   ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
       
   195   ///for the documentation of a Dijkstra traits class.
       
   196 #ifdef DOXYGEN
   189 #ifdef DOXYGEN
   197   template <typename GR, typename LM, typename TR>
   190   template <typename GR, typename LM, typename TR>
   198 #else
   191 #else
   199   template <typename GR=ListDigraph,
   192   template <typename GR=ListDigraph,
   200             typename LM=typename GR::template ArcMap<int>,
   193             typename LM=typename GR::template ArcMap<int>,
   224     ///The heap type used by the algorithm.
   217     ///The heap type used by the algorithm.
   225     typedef typename TR::Heap Heap;
   218     typedef typename TR::Heap Heap;
   226     ///The operation traits class.
   219     ///The operation traits class.
   227     typedef typename TR::OperationTraits OperationTraits;
   220     typedef typename TR::OperationTraits OperationTraits;
   228 
   221 
   229     ///The traits class.
   222     ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
   230     typedef TR Traits;
   223     typedef TR Traits;
   231 
   224 
   232   private:
   225   private:
   233 
   226 
   234     typedef typename Digraph::Node Node;
   227     typedef typename Digraph::Node Node;
   306     ///\brief \ref named-templ-param "Named parameter" for setting
   299     ///\brief \ref named-templ-param "Named parameter" for setting
   307     ///PredMap type.
   300     ///PredMap type.
   308     ///
   301     ///
   309     ///\ref named-templ-param "Named parameter" for setting
   302     ///\ref named-templ-param "Named parameter" for setting
   310     ///PredMap type.
   303     ///PredMap type.
       
   304     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   311     template <class T>
   305     template <class T>
   312     struct SetPredMap
   306     struct SetPredMap
   313       : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
   307       : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
   314       typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
   308       typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
   315     };
   309     };
   326     ///\brief \ref named-templ-param "Named parameter" for setting
   320     ///\brief \ref named-templ-param "Named parameter" for setting
   327     ///DistMap type.
   321     ///DistMap type.
   328     ///
   322     ///
   329     ///\ref named-templ-param "Named parameter" for setting
   323     ///\ref named-templ-param "Named parameter" for setting
   330     ///DistMap type.
   324     ///DistMap type.
       
   325     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   331     template <class T>
   326     template <class T>
   332     struct SetDistMap
   327     struct SetDistMap
   333       : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
   328       : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
   334       typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
   329       typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
   335     };
   330     };
   346     ///\brief \ref named-templ-param "Named parameter" for setting
   341     ///\brief \ref named-templ-param "Named parameter" for setting
   347     ///ProcessedMap type.
   342     ///ProcessedMap type.
   348     ///
   343     ///
   349     ///\ref named-templ-param "Named parameter" for setting
   344     ///\ref named-templ-param "Named parameter" for setting
   350     ///ProcessedMap type.
   345     ///ProcessedMap type.
       
   346     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   351     template <class T>
   347     template <class T>
   352     struct SetProcessedMap
   348     struct SetProcessedMap
   353       : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
   349       : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
   354       typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
   350       typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
   355     };
   351     };
   386         LEMON_ASSERT(false, "Heap is not initialized");
   382         LEMON_ASSERT(false, "Heap is not initialized");
   387         return 0; // ignore warnings
   383         return 0; // ignore warnings
   388       }
   384       }
   389     };
   385     };
   390     ///\brief \ref named-templ-param "Named parameter" for setting
   386     ///\brief \ref named-templ-param "Named parameter" for setting
   391     ///heap and cross reference type
   387     ///heap and cross reference types
   392     ///
   388     ///
   393     ///\ref named-templ-param "Named parameter" for setting heap and cross
   389     ///\ref named-templ-param "Named parameter" for setting heap and cross
   394     ///reference type.
   390     ///reference types. If this named parameter is used, then external
       
   391     ///heap and cross reference objects must be passed to the algorithm
       
   392     ///using the \ref heap() function before calling \ref run(Node) "run()"
       
   393     ///or \ref init().
       
   394     ///\sa SetStandardHeap
   395     template <class H, class CR = typename Digraph::template NodeMap<int> >
   395     template <class H, class CR = typename Digraph::template NodeMap<int> >
   396     struct SetHeap
   396     struct SetHeap
   397       : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
   397       : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
   398       typedef Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > Create;
   398       typedef Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > Create;
   399     };
   399     };
   409       {
   409       {
   410         return new Heap(R);
   410         return new Heap(R);
   411       }
   411       }
   412     };
   412     };
   413     ///\brief \ref named-templ-param "Named parameter" for setting
   413     ///\brief \ref named-templ-param "Named parameter" for setting
   414     ///heap and cross reference type with automatic allocation
   414     ///heap and cross reference types with automatic allocation
   415     ///
   415     ///
   416     ///\ref named-templ-param "Named parameter" for setting heap and cross
   416     ///\ref named-templ-param "Named parameter" for setting heap and cross
   417     ///reference type. It can allocate the heap and the cross reference
   417     ///reference types with automatic allocation.
   418     ///object if the cross reference's constructor waits for the digraph as
   418     ///They should have standard constructor interfaces to be able to
   419     ///parameter and the heap's constructor waits for the cross reference.
   419     ///automatically created by the algorithm (i.e. the digraph should be
       
   420     ///passed to the constructor of the cross reference and the cross
       
   421     ///reference should be passed to the constructor of the heap).
       
   422     ///However external heap and cross reference objects could also be
       
   423     ///passed to the algorithm using the \ref heap() function before
       
   424     ///calling \ref run(Node) "run()" or \ref init().
       
   425     ///\sa SetHeap
   420     template <class H, class CR = typename Digraph::template NodeMap<int> >
   426     template <class H, class CR = typename Digraph::template NodeMap<int> >
   421     struct SetStandardHeap
   427     struct SetStandardHeap
   422       : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
   428       : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
   423       typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> >
   429       typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> >
   424       Create;
   430       Create;
   484     }
   490     }
   485 
   491 
   486     ///Sets the map that stores the predecessor arcs.
   492     ///Sets the map that stores the predecessor arcs.
   487 
   493 
   488     ///Sets the map that stores the predecessor arcs.
   494     ///Sets the map that stores the predecessor arcs.
   489     ///If you don't use this function before calling \ref run(),
   495     ///If you don't use this function before calling \ref run(Node) "run()"
   490     ///it will allocate one. The destructor deallocates this
   496     ///or \ref init(), an instance will be allocated automatically.
   491     ///automatically allocated map, of course.
   497     ///The destructor deallocates this automatically allocated map,
       
   498     ///of course.
   492     ///\return <tt> (*this) </tt>
   499     ///\return <tt> (*this) </tt>
   493     Dijkstra &predMap(PredMap &m)
   500     Dijkstra &predMap(PredMap &m)
   494     {
   501     {
   495       if(local_pred) {
   502       if(local_pred) {
   496         delete _pred;
   503         delete _pred;
   501     }
   508     }
   502 
   509 
   503     ///Sets the map that indicates which nodes are processed.
   510     ///Sets the map that indicates which nodes are processed.
   504 
   511 
   505     ///Sets the map that indicates which nodes are processed.
   512     ///Sets the map that indicates which nodes are processed.
   506     ///If you don't use this function before calling \ref run(),
   513     ///If you don't use this function before calling \ref run(Node) "run()"
   507     ///it will allocate one. The destructor deallocates this
   514     ///or \ref init(), an instance will be allocated automatically.
   508     ///automatically allocated map, of course.
   515     ///The destructor deallocates this automatically allocated map,
       
   516     ///of course.
   509     ///\return <tt> (*this) </tt>
   517     ///\return <tt> (*this) </tt>
   510     Dijkstra &processedMap(ProcessedMap &m)
   518     Dijkstra &processedMap(ProcessedMap &m)
   511     {
   519     {
   512       if(local_processed) {
   520       if(local_processed) {
   513         delete _processed;
   521         delete _processed;
   519 
   527 
   520     ///Sets the map that stores the distances of the nodes.
   528     ///Sets the map that stores the distances of the nodes.
   521 
   529 
   522     ///Sets the map that stores the distances of the nodes calculated by the
   530     ///Sets the map that stores the distances of the nodes calculated by the
   523     ///algorithm.
   531     ///algorithm.
   524     ///If you don't use this function before calling \ref run(),
   532     ///If you don't use this function before calling \ref run(Node) "run()"
   525     ///it will allocate one. The destructor deallocates this
   533     ///or \ref init(), an instance will be allocated automatically.
   526     ///automatically allocated map, of course.
   534     ///The destructor deallocates this automatically allocated map,
       
   535     ///of course.
   527     ///\return <tt> (*this) </tt>
   536     ///\return <tt> (*this) </tt>
   528     Dijkstra &distMap(DistMap &m)
   537     Dijkstra &distMap(DistMap &m)
   529     {
   538     {
   530       if(local_dist) {
   539       if(local_dist) {
   531         delete _dist;
   540         delete _dist;
   536     }
   545     }
   537 
   546 
   538     ///Sets the heap and the cross reference used by algorithm.
   547     ///Sets the heap and the cross reference used by algorithm.
   539 
   548 
   540     ///Sets the heap and the cross reference used by algorithm.
   549     ///Sets the heap and the cross reference used by algorithm.
   541     ///If you don't use this function before calling \ref run(),
   550     ///If you don't use this function before calling \ref run(Node) "run()"
   542     ///it will allocate one. The destructor deallocates this
   551     ///or \ref init(), heap and cross reference instances will be
   543     ///automatically allocated heap and cross reference, of course.
   552     ///allocated automatically.
       
   553     ///The destructor deallocates these automatically allocated objects,
       
   554     ///of course.
   544     ///\return <tt> (*this) </tt>
   555     ///\return <tt> (*this) </tt>
   545     Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
   556     Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
   546     {
   557     {
   547       if(local_heap_cross_ref) {
   558       if(local_heap_cross_ref) {
   548         delete _heap_cross_ref;
   559         delete _heap_cross_ref;
   565       _dist->set(v, dst);
   576       _dist->set(v, dst);
   566     }
   577     }
   567 
   578 
   568   public:
   579   public:
   569 
   580 
   570     ///\name Execution control
   581     ///\name Execution Control
   571     ///The simplest way to execute the algorithm is to use one of the
   582     ///The simplest way to execute the %Dijkstra algorithm is to use
   572     ///member functions called \ref lemon::Dijkstra::run() "run()".
   583     ///one of the member functions called \ref run(Node) "run()".\n
   573     ///\n
   584     ///If you need more control on the execution, first you have to call
   574     ///If you need more control on the execution, first you must call
   585     ///\ref init(), then you can add several source nodes with
   575     ///\ref lemon::Dijkstra::init() "init()", then you can add several
   586     ///\ref addSource(). Finally the actual path computation can be
   576     ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
   587     ///performed with one of the \ref start() functions.
   577     ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
       
   578     ///actual path computation.
       
   579 
   588 
   580     ///@{
   589     ///@{
   581 
   590 
       
   591     ///\brief Initializes the internal data structures.
       
   592     ///
   582     ///Initializes the internal data structures.
   593     ///Initializes the internal data structures.
   583 
       
   584     ///Initializes the internal data structures.
       
   585     ///
       
   586     void init()
   594     void init()
   587     {
   595     {
   588       create_maps();
   596       create_maps();
   589       _heap->clear();
   597       _heap->clear();
   590       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
   598       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
   656     Node nextNode() const
   664     Node nextNode() const
   657     {
   665     {
   658       return !_heap->empty()?_heap->top():INVALID;
   666       return !_heap->empty()?_heap->top():INVALID;
   659     }
   667     }
   660 
   668 
   661     ///\brief Returns \c false if there are nodes
   669     ///Returns \c false if there are nodes to be processed.
   662     ///to be processed.
   670 
   663     ///
   671     ///Returns \c false if there are nodes to be processed
   664     ///Returns \c false if there are nodes
   672     ///in the priority heap.
   665     ///to be processed in the priority heap.
       
   666     bool emptyQueue() const { return _heap->empty(); }
   673     bool emptyQueue() const { return _heap->empty(); }
   667 
   674 
   668     ///Returns the number of the nodes to be processed in the priority heap
   675     ///Returns the number of the nodes to be processed.
   669 
   676 
   670     ///Returns the number of the nodes to be processed in the priority heap.
   677     ///Returns the number of the nodes to be processed
   671     ///
   678     ///in the priority heap.
   672     int queueSize() const { return _heap->size(); }
   679     int queueSize() const { return _heap->size(); }
   673 
   680 
   674     ///Executes the algorithm.
   681     ///Executes the algorithm.
   675 
   682 
   676     ///Executes the algorithm.
   683     ///Executes the algorithm.
   787     }
   794     }
   788 
   795 
   789     ///@}
   796     ///@}
   790 
   797 
   791     ///\name Query Functions
   798     ///\name Query Functions
   792     ///The result of the %Dijkstra algorithm can be obtained using these
   799     ///The results of the %Dijkstra algorithm can be obtained using these
   793     ///functions.\n
   800     ///functions.\n
   794     ///Either \ref lemon::Dijkstra::run() "run()" or
   801     ///Either \ref run(Node) "run()" or \ref start() should be called
   795     ///\ref lemon::Dijkstra::start() "start()" must be called before
   802     ///before using them.
   796     ///using them.
       
   797 
   803 
   798     ///@{
   804     ///@{
   799 
   805 
   800     ///The shortest path to a node.
   806     ///The shortest path to a node.
   801 
   807 
   802     ///Returns the shortest path to a node.
   808     ///Returns the shortest path to a node.
   803     ///
   809     ///
   804     ///\warning \c t should be reachable from the root(s).
   810     ///\warning \c t should be reached from the root(s).
   805     ///
   811     ///
   806     ///\pre Either \ref run() or \ref start() must be called before
   812     ///\pre Either \ref run(Node) "run()" or \ref init()
   807     ///using this function.
   813     ///must be called before using this function.
   808     Path path(Node t) const { return Path(*G, *_pred, t); }
   814     Path path(Node t) const { return Path(*G, *_pred, t); }
   809 
   815 
   810     ///The distance of a node from the root(s).
   816     ///The distance of a node from the root(s).
   811 
   817 
   812     ///Returns the distance of a node from the root(s).
   818     ///Returns the distance of a node from the root(s).
   813     ///
   819     ///
   814     ///\warning If node \c v is not reachable from the root(s), then
   820     ///\warning If node \c v is not reached from the root(s), then
   815     ///the return value of this function is undefined.
   821     ///the return value of this function is undefined.
   816     ///
   822     ///
   817     ///\pre Either \ref run() or \ref start() must be called before
   823     ///\pre Either \ref run(Node) "run()" or \ref init()
   818     ///using this function.
   824     ///must be called before using this function.
   819     Value dist(Node v) const { return (*_dist)[v]; }
   825     Value dist(Node v) const { return (*_dist)[v]; }
   820 
   826 
   821     ///Returns the 'previous arc' of the shortest path tree for a node.
   827     ///Returns the 'previous arc' of the shortest path tree for a node.
   822 
   828 
   823     ///This function returns the 'previous arc' of the shortest path
   829     ///This function returns the 'previous arc' of the shortest path
   824     ///tree for the node \c v, i.e. it returns the last arc of a
   830     ///tree for the node \c v, i.e. it returns the last arc of a
   825     ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
   831     ///shortest path from a root to \c v. It is \c INVALID if \c v
   826     ///is not reachable from the root(s) or if \c v is a root.
   832     ///is not reached from the root(s) or if \c v is a root.
   827     ///
   833     ///
   828     ///The shortest path tree used here is equal to the shortest path
   834     ///The shortest path tree used here is equal to the shortest path
   829     ///tree used in \ref predNode().
   835     ///tree used in \ref predNode().
   830     ///
   836     ///
   831     ///\pre Either \ref run() or \ref start() must be called before
   837     ///\pre Either \ref run(Node) "run()" or \ref init()
   832     ///using this function.
   838     ///must be called before using this function.
   833     Arc predArc(Node v) const { return (*_pred)[v]; }
   839     Arc predArc(Node v) const { return (*_pred)[v]; }
   834 
   840 
   835     ///Returns the 'previous node' of the shortest path tree for a node.
   841     ///Returns the 'previous node' of the shortest path tree for a node.
   836 
   842 
   837     ///This function returns the 'previous node' of the shortest path
   843     ///This function returns the 'previous node' of the shortest path
   838     ///tree for the node \c v, i.e. it returns the last but one node
   844     ///tree for the node \c v, i.e. it returns the last but one node
   839     ///from a shortest path from the root(s) to \c v. It is \c INVALID
   845     ///from a shortest path from a root to \c v. It is \c INVALID
   840     ///if \c v is not reachable from the root(s) or if \c v is a root.
   846     ///if \c v is not reached from the root(s) or if \c v is a root.
   841     ///
   847     ///
   842     ///The shortest path tree used here is equal to the shortest path
   848     ///The shortest path tree used here is equal to the shortest path
   843     ///tree used in \ref predArc().
   849     ///tree used in \ref predArc().
   844     ///
   850     ///
   845     ///\pre Either \ref run() or \ref start() must be called before
   851     ///\pre Either \ref run(Node) "run()" or \ref init()
   846     ///using this function.
   852     ///must be called before using this function.
   847     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   853     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   848                                   G->source((*_pred)[v]); }
   854                                   G->source((*_pred)[v]); }
   849 
   855 
   850     ///\brief Returns a const reference to the node map that stores the
   856     ///\brief Returns a const reference to the node map that stores the
   851     ///distances of the nodes.
   857     ///distances of the nodes.
   852     ///
   858     ///
   853     ///Returns a const reference to the node map that stores the distances
   859     ///Returns a const reference to the node map that stores the distances
   854     ///of the nodes calculated by the algorithm.
   860     ///of the nodes calculated by the algorithm.
   855     ///
   861     ///
   856     ///\pre Either \ref run() or \ref init()
   862     ///\pre Either \ref run(Node) "run()" or \ref init()
   857     ///must be called before using this function.
   863     ///must be called before using this function.
   858     const DistMap &distMap() const { return *_dist;}
   864     const DistMap &distMap() const { return *_dist;}
   859 
   865 
   860     ///\brief Returns a const reference to the node map that stores the
   866     ///\brief Returns a const reference to the node map that stores the
   861     ///predecessor arcs.
   867     ///predecessor arcs.
   862     ///
   868     ///
   863     ///Returns a const reference to the node map that stores the predecessor
   869     ///Returns a const reference to the node map that stores the predecessor
   864     ///arcs, which form the shortest path tree.
   870     ///arcs, which form the shortest path tree.
   865     ///
   871     ///
   866     ///\pre Either \ref run() or \ref init()
   872     ///\pre Either \ref run(Node) "run()" or \ref init()
   867     ///must be called before using this function.
   873     ///must be called before using this function.
   868     const PredMap &predMap() const { return *_pred;}
   874     const PredMap &predMap() const { return *_pred;}
   869 
   875 
   870     ///Checks if a node is reachable from the root(s).
   876     ///Checks if a node is reached from the root(s).
   871 
   877 
   872     ///Returns \c true if \c v is reachable from the root(s).
   878     ///Returns \c true if \c v is reached from the root(s).
   873     ///\pre Either \ref run() or \ref start()
   879     ///
       
   880     ///\pre Either \ref run(Node) "run()" or \ref init()
   874     ///must be called before using this function.
   881     ///must be called before using this function.
   875     bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
   882     bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
   876                                         Heap::PRE_HEAP; }
   883                                         Heap::PRE_HEAP; }
   877 
   884 
   878     ///Checks if a node is processed.
   885     ///Checks if a node is processed.
   879 
   886 
   880     ///Returns \c true if \c v is processed, i.e. the shortest
   887     ///Returns \c true if \c v is processed, i.e. the shortest
   881     ///path to \c v has already found.
   888     ///path to \c v has already found.
   882     ///\pre Either \ref run() or \ref init()
   889     ///
       
   890     ///\pre Either \ref run(Node) "run()" or \ref init()
   883     ///must be called before using this function.
   891     ///must be called before using this function.
   884     bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
   892     bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
   885                                           Heap::POST_HEAP; }
   893                                           Heap::POST_HEAP; }
   886 
   894 
   887     ///The current distance of a node from the root(s).
   895     ///The current distance of a node from the root(s).
   888 
   896 
   889     ///Returns the current distance of a node from the root(s).
   897     ///Returns the current distance of a node from the root(s).
   890     ///It may be decreased in the following processes.
   898     ///It may be decreased in the following processes.
   891     ///\pre Either \ref run() or \ref init()
   899     ///
       
   900     ///\pre Either \ref run(Node) "run()" or \ref init()
   892     ///must be called before using this function and
   901     ///must be called before using this function and
   893     ///node \c v must be reached but not necessarily processed.
   902     ///node \c v must be reached but not necessarily processed.
   894     Value currentDist(Node v) const {
   903     Value currentDist(Node v) const {
   895       return processed(v) ? (*_dist)[v] : (*_heap)[v];
   904       return processed(v) ? (*_dist)[v] : (*_heap)[v];
   896     }
   905     }
  1069 
  1078 
  1070   /// Auxiliary class for the function-type interface of Dijkstra algorithm.
  1079   /// Auxiliary class for the function-type interface of Dijkstra algorithm.
  1071 
  1080 
  1072   /// This auxiliary class is created to implement the
  1081   /// This auxiliary class is created to implement the
  1073   /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
  1082   /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
  1074   /// It does not have own \ref run() method, it uses the functions
  1083   /// It does not have own \ref run(Node) "run()" method, it uses the
  1075   /// and features of the plain \ref Dijkstra.
  1084   /// functions and features of the plain \ref Dijkstra.
  1076   ///
  1085   ///
  1077   /// This class should only be used through the \ref dijkstra() function,
  1086   /// This class should only be used through the \ref dijkstra() function,
  1078   /// which makes it easier to use the algorithm.
  1087   /// which makes it easier to use the algorithm.
  1079   template<class TR>
  1088   template<class TR>
  1080   class DijkstraWizard : public TR
  1089   class DijkstraWizard : public TR
  1265   ///  dijkstra(g,length).predMap(preds).distMap(dists).run(s);
  1274   ///  dijkstra(g,length).predMap(preds).distMap(dists).run(s);
  1266   ///
  1275   ///
  1267   ///  // Compute shortest path from s to t
  1276   ///  // Compute shortest path from s to t
  1268   ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
  1277   ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
  1269   ///\endcode
  1278   ///\endcode
  1270   ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
  1279   ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
  1271   ///to the end of the parameter list.
  1280   ///to the end of the parameter list.
  1272   ///\sa DijkstraWizard
  1281   ///\sa DijkstraWizard
  1273   ///\sa Dijkstra
  1282   ///\sa Dijkstra
  1274   template<class GR, class LM>
  1283   template<class GR, class LM>
  1275   DijkstraWizard<DijkstraWizardBase<GR,LM> >
  1284   DijkstraWizard<DijkstraWizardBase<GR,LM> >