lemon/dijkstra.h
author Peter Kovacs <kpeter@inf.elte.hu>
Wed, 01 Oct 2008 12:44:16 +0200
changeset 293 47fbc814aa31
parent 286 da414906fe21
parent 281 e9b4fbe163f5
child 290 f6899946c1ac
permissions -rw-r--r--
Change the parameter order in LGF reader and writer tools
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_DIJKSTRA_H
    20 #define LEMON_DIJKSTRA_H
    21 
    22 ///\ingroup shortest_path
    23 ///\file
    24 ///\brief Dijkstra algorithm.
    25 
    26 #include <limits>
    27 #include <lemon/list_graph.h>
    28 #include <lemon/bin_heap.h>
    29 #include <lemon/bits/path_dump.h>
    30 #include <lemon/core.h>
    31 #include <lemon/error.h>
    32 #include <lemon/maps.h>
    33 #include <lemon/path.h>
    34 
    35 namespace lemon {
    36 
    37   /// \brief Default operation traits for the Dijkstra algorithm class.
    38   ///
    39   /// This operation traits class defines all computational operations and
    40   /// constants which are used in the Dijkstra algorithm.
    41   template <typename Value>
    42   struct DijkstraDefaultOperationTraits {
    43     /// \brief Gives back the zero value of the type.
    44     static Value zero() {
    45       return static_cast<Value>(0);
    46     }
    47     /// \brief Gives back the sum of the given two elements.
    48     static Value plus(const Value& left, const Value& right) {
    49       return left + right;
    50     }
    51     /// \brief Gives back true only if the first value is less than the second.
    52     static bool less(const Value& left, const Value& right) {
    53       return left < right;
    54     }
    55   };
    56 
    57   /// \brief Widest path operation traits for the Dijkstra algorithm class.
    58   ///
    59   /// This operation traits class defines all computational operations and
    60   /// constants which are used in the Dijkstra algorithm for widest path
    61   /// computation.
    62   ///
    63   /// \see DijkstraDefaultOperationTraits
    64   template <typename Value>
    65   struct DijkstraWidestPathOperationTraits {
    66     /// \brief Gives back the maximum value of the type.
    67     static Value zero() {
    68       return std::numeric_limits<Value>::max();
    69     }
    70     /// \brief Gives back the minimum of the given two elements.
    71     static Value plus(const Value& left, const Value& right) {
    72       return std::min(left, right);
    73     }
    74     /// \brief Gives back true only if the first value is less than the second.
    75     static bool less(const Value& left, const Value& right) {
    76       return left < right;
    77     }
    78   };
    79 
    80   ///Default traits class of Dijkstra class.
    81 
    82   ///Default traits class of Dijkstra class.
    83   ///\tparam GR The type of the digraph.
    84   ///\tparam LM The type of the length map.
    85   template<class GR, class LM>
    86   struct DijkstraDefaultTraits
    87   {
    88     ///The type of the digraph the algorithm runs on.
    89     typedef GR Digraph;
    90 
    91     ///The type of the map that stores the arc lengths.
    92 
    93     ///The type of the map that stores the arc lengths.
    94     ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    95     typedef LM LengthMap;
    96     ///The type of the length of the arcs.
    97     typedef typename LM::Value Value;
    98 
    99     /// Operation traits for Dijkstra algorithm.
   100 
   101     /// This class defines the operations that are used in the algorithm.
   102     /// \see DijkstraDefaultOperationTraits
   103     typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
   104 
   105     /// The cross reference type used by the heap.
   106 
   107     /// The cross reference type used by the heap.
   108     /// Usually it is \c Digraph::NodeMap<int>.
   109     typedef typename Digraph::template NodeMap<int> HeapCrossRef;
   110     ///Instantiates a \ref HeapCrossRef.
   111 
   112     ///This function instantiates a \ref HeapCrossRef.
   113     /// \param g is the digraph, to which we would like to define the
   114     /// \ref HeapCrossRef.
   115     static HeapCrossRef *createHeapCrossRef(const Digraph &g)
   116     {
   117       return new HeapCrossRef(g);
   118     }
   119 
   120     ///The heap type used by the Dijkstra algorithm.
   121 
   122     ///The heap type used by the Dijkstra algorithm.
   123     ///
   124     ///\sa BinHeap
   125     ///\sa Dijkstra
   126     typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
   127     ///Instantiates a \ref Heap.
   128 
   129     ///This function instantiates a \ref Heap.
   130     static Heap *createHeap(HeapCrossRef& r)
   131     {
   132       return new Heap(r);
   133     }
   134 
   135     ///\brief The type of the map that stores the predecessor
   136     ///arcs of the shortest paths.
   137     ///
   138     ///The type of the map that stores the predecessor
   139     ///arcs of the shortest paths.
   140     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   141     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   142     ///Instantiates a \ref PredMap.
   143 
   144     ///This function instantiates a \ref PredMap.
   145     ///\param g is the digraph, to which we would like to define the
   146     ///\ref PredMap.
   147     static PredMap *createPredMap(const Digraph &g)
   148     {
   149       return new PredMap(g);
   150     }
   151 
   152     ///The type of the map that indicates which nodes are processed.
   153 
   154     ///The type of the map that indicates which nodes are processed.
   155     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   156     ///By default it is a NullMap.
   157     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   158     ///Instantiates a \ref ProcessedMap.
   159 
   160     ///This function instantiates a \ref ProcessedMap.
   161     ///\param g is the digraph, to which
   162     ///we would like to define the \ref ProcessedMap
   163 #ifdef DOXYGEN
   164     static ProcessedMap *createProcessedMap(const Digraph &g)
   165 #else
   166     static ProcessedMap *createProcessedMap(const Digraph &)
   167 #endif
   168     {
   169       return new ProcessedMap();
   170     }
   171 
   172     ///The type of the map that stores the distances of the nodes.
   173 
   174     ///The type of the map that stores the distances of the nodes.
   175     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   176     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
   177     ///Instantiates a \ref DistMap.
   178 
   179     ///This function instantiates a \ref DistMap.
   180     ///\param g is the digraph, to which we would like to define
   181     ///the \ref DistMap
   182     static DistMap *createDistMap(const Digraph &g)
   183     {
   184       return new DistMap(g);
   185     }
   186   };
   187 
   188   ///%Dijkstra algorithm class.
   189 
   190   /// \ingroup shortest_path
   191   ///This class provides an efficient implementation of the %Dijkstra algorithm.
   192   ///
   193   ///The arc lengths are passed to the algorithm using a
   194   ///\ref concepts::ReadMap "ReadMap",
   195   ///so it is easy to change it to any kind of length.
   196   ///The type of the length is determined by the
   197   ///\ref concepts::ReadMap::Value "Value" of the length map.
   198   ///It is also possible to change the underlying priority heap.
   199   ///
   200   ///There is also a \ref dijkstra() "function-type interface" for the
   201   ///%Dijkstra algorithm, which is convenient in the simplier cases and
   202   ///it can be used easier.
   203   ///
   204   ///\tparam GR The type of the digraph the algorithm runs on.
   205   ///The default value is \ref ListDigraph.
   206   ///The value of GR is not used directly by \ref Dijkstra, it is only
   207   ///passed to \ref DijkstraDefaultTraits.
   208   ///\tparam LM A readable arc map that determines the lengths of the
   209   ///arcs. It is read once for each arc, so the map may involve in
   210   ///relatively time consuming process to compute the arc lengths if
   211   ///it is necessary. The default map type is \ref
   212   ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
   213   ///The value of LM is not used directly by \ref Dijkstra, it is only
   214   ///passed to \ref DijkstraDefaultTraits.
   215   ///\tparam TR Traits class to set various data types used by the algorithm.
   216   ///The default traits class is \ref DijkstraDefaultTraits
   217   ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
   218   ///for the documentation of a Dijkstra traits class.
   219 #ifdef DOXYGEN
   220   template <typename GR, typename LM, typename TR>
   221 #else
   222   template <typename GR=ListDigraph,
   223             typename LM=typename GR::template ArcMap<int>,
   224             typename TR=DijkstraDefaultTraits<GR,LM> >
   225 #endif
   226   class Dijkstra {
   227   public:
   228     ///\ref Exception for uninitialized parameters.
   229 
   230     ///This error represents problems in the initialization of the
   231     ///parameters of the algorithm.
   232     class UninitializedParameter : public lemon::UninitializedParameter {
   233     public:
   234       virtual const char* what() const throw() {
   235         return "lemon::Dijkstra::UninitializedParameter";
   236       }
   237     };
   238 
   239     ///The type of the digraph the algorithm runs on.
   240     typedef typename TR::Digraph Digraph;
   241 
   242     ///The type of the length of the arcs.
   243     typedef typename TR::LengthMap::Value Value;
   244     ///The type of the map that stores the arc lengths.
   245     typedef typename TR::LengthMap LengthMap;
   246     ///\brief The type of the map that stores the predecessor arcs of the
   247     ///shortest paths.
   248     typedef typename TR::PredMap PredMap;
   249     ///The type of the map that stores the distances of the nodes.
   250     typedef typename TR::DistMap DistMap;
   251     ///The type of the map that indicates which nodes are processed.
   252     typedef typename TR::ProcessedMap ProcessedMap;
   253     ///The type of the paths.
   254     typedef PredMapPath<Digraph, PredMap> Path;
   255     ///The cross reference type used for the current heap.
   256     typedef typename TR::HeapCrossRef HeapCrossRef;
   257     ///The heap type used by the algorithm.
   258     typedef typename TR::Heap Heap;
   259     ///The operation traits class.
   260     typedef typename TR::OperationTraits OperationTraits;
   261 
   262     ///The traits class.
   263     typedef TR Traits;
   264 
   265   private:
   266 
   267     typedef typename Digraph::Node Node;
   268     typedef typename Digraph::NodeIt NodeIt;
   269     typedef typename Digraph::Arc Arc;
   270     typedef typename Digraph::OutArcIt OutArcIt;
   271 
   272     //Pointer to the underlying digraph.
   273     const Digraph *G;
   274     //Pointer to the length map.
   275     const LengthMap *length;
   276     //Pointer to the map of predecessors arcs.
   277     PredMap *_pred;
   278     //Indicates if _pred is locally allocated (true) or not.
   279     bool local_pred;
   280     //Pointer to the map of distances.
   281     DistMap *_dist;
   282     //Indicates if _dist is locally allocated (true) or not.
   283     bool local_dist;
   284     //Pointer to the map of processed status of the nodes.
   285     ProcessedMap *_processed;
   286     //Indicates if _processed is locally allocated (true) or not.
   287     bool local_processed;
   288     //Pointer to the heap cross references.
   289     HeapCrossRef *_heap_cross_ref;
   290     //Indicates if _heap_cross_ref is locally allocated (true) or not.
   291     bool local_heap_cross_ref;
   292     //Pointer to the heap.
   293     Heap *_heap;
   294     //Indicates if _heap is locally allocated (true) or not.
   295     bool local_heap;
   296 
   297     //Creates the maps if necessary.
   298     void create_maps()
   299     {
   300       if(!_pred) {
   301         local_pred = true;
   302         _pred = Traits::createPredMap(*G);
   303       }
   304       if(!_dist) {
   305         local_dist = true;
   306         _dist = Traits::createDistMap(*G);
   307       }
   308       if(!_processed) {
   309         local_processed = true;
   310         _processed = Traits::createProcessedMap(*G);
   311       }
   312       if (!_heap_cross_ref) {
   313         local_heap_cross_ref = true;
   314         _heap_cross_ref = Traits::createHeapCrossRef(*G);
   315       }
   316       if (!_heap) {
   317         local_heap = true;
   318         _heap = Traits::createHeap(*_heap_cross_ref);
   319       }
   320     }
   321 
   322   public:
   323 
   324     typedef Dijkstra Create;
   325 
   326     ///\name Named template parameters
   327 
   328     ///@{
   329 
   330     template <class T>
   331     struct SetPredMapTraits : public Traits {
   332       typedef T PredMap;
   333       static PredMap *createPredMap(const Digraph &)
   334       {
   335         throw UninitializedParameter();
   336       }
   337     };
   338     ///\brief \ref named-templ-param "Named parameter" for setting
   339     ///\ref PredMap type.
   340     ///
   341     ///\ref named-templ-param "Named parameter" for setting
   342     ///\ref PredMap type.
   343     template <class T>
   344     struct SetPredMap
   345       : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
   346       typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
   347     };
   348 
   349     template <class T>
   350     struct SetDistMapTraits : public Traits {
   351       typedef T DistMap;
   352       static DistMap *createDistMap(const Digraph &)
   353       {
   354         throw UninitializedParameter();
   355       }
   356     };
   357     ///\brief \ref named-templ-param "Named parameter" for setting
   358     ///\ref DistMap type.
   359     ///
   360     ///\ref named-templ-param "Named parameter" for setting
   361     ///\ref DistMap type.
   362     template <class T>
   363     struct SetDistMap
   364       : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
   365       typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
   366     };
   367 
   368     template <class T>
   369     struct SetProcessedMapTraits : public Traits {
   370       typedef T ProcessedMap;
   371       static ProcessedMap *createProcessedMap(const Digraph &)
   372       {
   373         throw UninitializedParameter();
   374       }
   375     };
   376     ///\brief \ref named-templ-param "Named parameter" for setting
   377     ///\ref ProcessedMap type.
   378     ///
   379     ///\ref named-templ-param "Named parameter" for setting
   380     ///\ref ProcessedMap type.
   381     template <class T>
   382     struct SetProcessedMap
   383       : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
   384       typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
   385     };
   386 
   387     struct SetStandardProcessedMapTraits : public Traits {
   388       typedef typename Digraph::template NodeMap<bool> ProcessedMap;
   389       static ProcessedMap *createProcessedMap(const Digraph &g)
   390       {
   391         return new ProcessedMap(g);
   392       }
   393     };
   394     ///\brief \ref named-templ-param "Named parameter" for setting
   395     ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   396     ///
   397     ///\ref named-templ-param "Named parameter" for setting
   398     ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   399     ///If you don't set it explicitly, it will be automatically allocated.
   400     struct SetStandardProcessedMap
   401       : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
   402       typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >
   403       Create;
   404     };
   405 
   406     template <class H, class CR>
   407     struct SetHeapTraits : public Traits {
   408       typedef CR HeapCrossRef;
   409       typedef H Heap;
   410       static HeapCrossRef *createHeapCrossRef(const Digraph &) {
   411         throw UninitializedParameter();
   412       }
   413       static Heap *createHeap(HeapCrossRef &)
   414       {
   415         throw UninitializedParameter();
   416       }
   417     };
   418     ///\brief \ref named-templ-param "Named parameter" for setting
   419     ///heap and cross reference type
   420     ///
   421     ///\ref named-templ-param "Named parameter" for setting heap and cross
   422     ///reference type.
   423     template <class H, class CR = typename Digraph::template NodeMap<int> >
   424     struct SetHeap
   425       : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
   426       typedef Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > Create;
   427     };
   428 
   429     template <class H, class CR>
   430     struct SetStandardHeapTraits : public Traits {
   431       typedef CR HeapCrossRef;
   432       typedef H Heap;
   433       static HeapCrossRef *createHeapCrossRef(const Digraph &G) {
   434         return new HeapCrossRef(G);
   435       }
   436       static Heap *createHeap(HeapCrossRef &R)
   437       {
   438         return new Heap(R);
   439       }
   440     };
   441     ///\brief \ref named-templ-param "Named parameter" for setting
   442     ///heap and cross reference type with automatic allocation
   443     ///
   444     ///\ref named-templ-param "Named parameter" for setting heap and cross
   445     ///reference type. It can allocate the heap and the cross reference
   446     ///object if the cross reference's constructor waits for the digraph as
   447     ///parameter and the heap's constructor waits for the cross reference.
   448     template <class H, class CR = typename Digraph::template NodeMap<int> >
   449     struct SetStandardHeap
   450       : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
   451       typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> >
   452       Create;
   453     };
   454 
   455     template <class T>
   456     struct SetOperationTraitsTraits : public Traits {
   457       typedef T OperationTraits;
   458     };
   459 
   460     /// \brief \ref named-templ-param "Named parameter" for setting
   461     ///\ref OperationTraits type
   462     ///
   463     ///\ref named-templ-param "Named parameter" for setting
   464     ///\ref OperationTraits type.
   465     template <class T>
   466     struct SetOperationTraits
   467       : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
   468       typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >
   469       Create;
   470     };
   471 
   472     ///@}
   473 
   474   protected:
   475 
   476     Dijkstra() {}
   477 
   478   public:
   479 
   480     ///Constructor.
   481 
   482     ///Constructor.
   483     ///\param _g The digraph the algorithm runs on.
   484     ///\param _length The length map used by the algorithm.
   485     Dijkstra(const Digraph& _g, const LengthMap& _length) :
   486       G(&_g), length(&_length),
   487       _pred(NULL), local_pred(false),
   488       _dist(NULL), local_dist(false),
   489       _processed(NULL), local_processed(false),
   490       _heap_cross_ref(NULL), local_heap_cross_ref(false),
   491       _heap(NULL), local_heap(false)
   492     { }
   493 
   494     ///Destructor.
   495     ~Dijkstra()
   496     {
   497       if(local_pred) delete _pred;
   498       if(local_dist) delete _dist;
   499       if(local_processed) delete _processed;
   500       if(local_heap_cross_ref) delete _heap_cross_ref;
   501       if(local_heap) delete _heap;
   502     }
   503 
   504     ///Sets the length map.
   505 
   506     ///Sets the length map.
   507     ///\return <tt> (*this) </tt>
   508     Dijkstra &lengthMap(const LengthMap &m)
   509     {
   510       length = &m;
   511       return *this;
   512     }
   513 
   514     ///Sets the map that stores the predecessor arcs.
   515 
   516     ///Sets the map that stores the predecessor arcs.
   517     ///If you don't use this function before calling \ref run(),
   518     ///it will allocate one. The destructor deallocates this
   519     ///automatically allocated map, of course.
   520     ///\return <tt> (*this) </tt>
   521     Dijkstra &predMap(PredMap &m)
   522     {
   523       if(local_pred) {
   524         delete _pred;
   525         local_pred=false;
   526       }
   527       _pred = &m;
   528       return *this;
   529     }
   530 
   531     ///Sets the map that indicates which nodes are processed.
   532 
   533     ///Sets the map that indicates which nodes are processed.
   534     ///If you don't use this function before calling \ref run(),
   535     ///it will allocate one. The destructor deallocates this
   536     ///automatically allocated map, of course.
   537     ///\return <tt> (*this) </tt>
   538     Dijkstra &processedMap(ProcessedMap &m)
   539     {
   540       if(local_processed) {
   541         delete _processed;
   542         local_processed=false;
   543       }
   544       _processed = &m;
   545       return *this;
   546     }
   547 
   548     ///Sets the map that stores the distances of the nodes.
   549 
   550     ///Sets the map that stores the distances of the nodes calculated by the
   551     ///algorithm.
   552     ///If you don't use this function before calling \ref run(),
   553     ///it will allocate one. The destructor deallocates this
   554     ///automatically allocated map, of course.
   555     ///\return <tt> (*this) </tt>
   556     Dijkstra &distMap(DistMap &m)
   557     {
   558       if(local_dist) {
   559         delete _dist;
   560         local_dist=false;
   561       }
   562       _dist = &m;
   563       return *this;
   564     }
   565 
   566     ///Sets the heap and the cross reference used by algorithm.
   567 
   568     ///Sets the heap and the cross reference used by algorithm.
   569     ///If you don't use this function before calling \ref run(),
   570     ///it will allocate one. The destructor deallocates this
   571     ///automatically allocated heap and cross reference, of course.
   572     ///\return <tt> (*this) </tt>
   573     Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
   574     {
   575       if(local_heap_cross_ref) {
   576         delete _heap_cross_ref;
   577         local_heap_cross_ref=false;
   578       }
   579       _heap_cross_ref = &cr;
   580       if(local_heap) {
   581         delete _heap;
   582         local_heap=false;
   583       }
   584       _heap = &hp;
   585       return *this;
   586     }
   587 
   588   private:
   589 
   590     void finalizeNodeData(Node v,Value dst)
   591     {
   592       _processed->set(v,true);
   593       _dist->set(v, dst);
   594     }
   595 
   596   public:
   597 
   598     ///\name Execution control
   599     ///The simplest way to execute the algorithm is to use one of the
   600     ///member functions called \ref lemon::Dijkstra::run() "run()".
   601     ///\n
   602     ///If you need more control on the execution, first you must call
   603     ///\ref lemon::Dijkstra::init() "init()", then you can add several
   604     ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
   605     ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
   606     ///actual path computation.
   607 
   608     ///@{
   609 
   610     ///Initializes the internal data structures.
   611 
   612     ///Initializes the internal data structures.
   613     ///
   614     void init()
   615     {
   616       create_maps();
   617       _heap->clear();
   618       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
   619         _pred->set(u,INVALID);
   620         _processed->set(u,false);
   621         _heap_cross_ref->set(u,Heap::PRE_HEAP);
   622       }
   623     }
   624 
   625     ///Adds a new source node.
   626 
   627     ///Adds a new source node to the priority heap.
   628     ///The optional second parameter is the initial distance of the node.
   629     ///
   630     ///The function checks if the node has already been added to the heap and
   631     ///it is pushed to the heap only if either it was not in the heap
   632     ///or the shortest path found till then is shorter than \c dst.
   633     void addSource(Node s,Value dst=OperationTraits::zero())
   634     {
   635       if(_heap->state(s) != Heap::IN_HEAP) {
   636         _heap->push(s,dst);
   637       } else if(OperationTraits::less((*_heap)[s], dst)) {
   638         _heap->set(s,dst);
   639         _pred->set(s,INVALID);
   640       }
   641     }
   642 
   643     ///Processes the next node in the priority heap
   644 
   645     ///Processes the next node in the priority heap.
   646     ///
   647     ///\return The processed node.
   648     ///
   649     ///\warning The priority heap must not be empty.
   650     Node processNextNode()
   651     {
   652       Node v=_heap->top();
   653       Value oldvalue=_heap->prio();
   654       _heap->pop();
   655       finalizeNodeData(v,oldvalue);
   656 
   657       for(OutArcIt e(*G,v); e!=INVALID; ++e) {
   658         Node w=G->target(e);
   659         switch(_heap->state(w)) {
   660         case Heap::PRE_HEAP:
   661           _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
   662           _pred->set(w,e);
   663           break;
   664         case Heap::IN_HEAP:
   665           {
   666             Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
   667             if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
   668               _heap->decrease(w, newvalue);
   669               _pred->set(w,e);
   670             }
   671           }
   672           break;
   673         case Heap::POST_HEAP:
   674           break;
   675         }
   676       }
   677       return v;
   678     }
   679 
   680     ///The next node to be processed.
   681 
   682     ///Returns the next node to be processed or \c INVALID if the
   683     ///priority heap is empty.
   684     Node nextNode() const
   685     {
   686       return !_heap->empty()?_heap->top():INVALID;
   687     }
   688 
   689     ///\brief Returns \c false if there are nodes
   690     ///to be processed.
   691     ///
   692     ///Returns \c false if there are nodes
   693     ///to be processed in the priority heap.
   694     bool emptyQueue() const { return _heap->empty(); }
   695 
   696     ///Returns the number of the nodes to be processed in the priority heap
   697 
   698     ///Returns the number of the nodes to be processed in the priority heap.
   699     ///
   700     int queueSize() const { return _heap->size(); }
   701 
   702     ///Executes the algorithm.
   703 
   704     ///Executes the algorithm.
   705     ///
   706     ///This method runs the %Dijkstra algorithm from the root node(s)
   707     ///in order to compute the shortest path to each node.
   708     ///
   709     ///The algorithm computes
   710     ///- the shortest path tree (forest),
   711     ///- the distance of each node from the root(s).
   712     ///
   713     ///\pre init() must be called and at least one root node should be
   714     ///added with addSource() before using this function.
   715     ///
   716     ///\note <tt>d.start()</tt> is just a shortcut of the following code.
   717     ///\code
   718     ///  while ( !d.emptyQueue() ) {
   719     ///    d.processNextNode();
   720     ///  }
   721     ///\endcode
   722     void start()
   723     {
   724       while ( !emptyQueue() ) processNextNode();
   725     }
   726 
   727     ///Executes the algorithm until the given target node is processed.
   728 
   729     ///Executes the algorithm until the given target node is processed.
   730     ///
   731     ///This method runs the %Dijkstra algorithm from the root node(s)
   732     ///in order to compute the shortest path to \c t.
   733     ///
   734     ///The algorithm computes
   735     ///- the shortest path to \c t,
   736     ///- the distance of \c t from the root(s).
   737     ///
   738     ///\pre init() must be called and at least one root node should be
   739     ///added with addSource() before using this function.
   740     void start(Node t)
   741     {
   742       while ( !_heap->empty() && _heap->top()!=t ) processNextNode();
   743       if ( !_heap->empty() ) {
   744         finalizeNodeData(_heap->top(),_heap->prio());
   745         _heap->pop();
   746       }
   747     }
   748 
   749     ///Executes the algorithm until a condition is met.
   750 
   751     ///Executes the algorithm until a condition is met.
   752     ///
   753     ///This method runs the %Dijkstra algorithm from the root node(s) in
   754     ///order to compute the shortest path to a node \c v with
   755     /// <tt>nm[v]</tt> true, if such a node can be found.
   756     ///
   757     ///\param nm A \c bool (or convertible) node map. The algorithm
   758     ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
   759     ///
   760     ///\return The reached node \c v with <tt>nm[v]</tt> true or
   761     ///\c INVALID if no such node was found.
   762     ///
   763     ///\pre init() must be called and at least one root node should be
   764     ///added with addSource() before using this function.
   765     template<class NodeBoolMap>
   766     Node start(const NodeBoolMap &nm)
   767     {
   768       while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
   769       if ( _heap->empty() ) return INVALID;
   770       finalizeNodeData(_heap->top(),_heap->prio());
   771       return _heap->top();
   772     }
   773 
   774     ///Runs the algorithm from the given source node.
   775 
   776     ///This method runs the %Dijkstra algorithm from node \c s
   777     ///in order to compute the shortest path to each node.
   778     ///
   779     ///The algorithm computes
   780     ///- the shortest path tree,
   781     ///- the distance of each node from the root.
   782     ///
   783     ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
   784     ///\code
   785     ///  d.init();
   786     ///  d.addSource(s);
   787     ///  d.start();
   788     ///\endcode
   789     void run(Node s) {
   790       init();
   791       addSource(s);
   792       start();
   793     }
   794 
   795     ///Finds the shortest path between \c s and \c t.
   796 
   797     ///This method runs the %Dijkstra algorithm from node \c s
   798     ///in order to compute the shortest path to node \c t
   799     ///(it stops searching when \c t is processed).
   800     ///
   801     ///\return \c true if \c t is reachable form \c s.
   802     ///
   803     ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
   804     ///shortcut of the following code.
   805     ///\code
   806     ///  d.init();
   807     ///  d.addSource(s);
   808     ///  d.start(t);
   809     ///\endcode
   810     bool run(Node s,Node t) {
   811       init();
   812       addSource(s);
   813       start(t);
   814       return (*_heap_cross_ref)[t] == Heap::POST_HEAP;
   815     }
   816 
   817     ///@}
   818 
   819     ///\name Query Functions
   820     ///The result of the %Dijkstra algorithm can be obtained using these
   821     ///functions.\n
   822     ///Either \ref lemon::Dijkstra::run() "run()" or
   823     ///\ref lemon::Dijkstra::start() "start()" must be called before
   824     ///using them.
   825 
   826     ///@{
   827 
   828     ///The shortest path to a node.
   829 
   830     ///Returns the shortest path to a node.
   831     ///
   832     ///\warning \c t should be reachable from the root(s).
   833     ///
   834     ///\pre Either \ref run() or \ref start() must be called before
   835     ///using this function.
   836     Path path(Node t) const { return Path(*G, *_pred, t); }
   837 
   838     ///The distance of a node from the root(s).
   839 
   840     ///Returns the distance of a node from the root(s).
   841     ///
   842     ///\warning If node \c v is not reachable from the root(s), then
   843     ///the return value of this function is undefined.
   844     ///
   845     ///\pre Either \ref run() or \ref start() must be called before
   846     ///using this function.
   847     Value dist(Node v) const { return (*_dist)[v]; }
   848 
   849     ///Returns the 'previous arc' of the shortest path tree for a node.
   850 
   851     ///This function returns the 'previous arc' of the shortest path
   852     ///tree for the node \c v, i.e. it returns the last arc of a
   853     ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
   854     ///is not reachable from the root(s) or if \c v is a root.
   855     ///
   856     ///The shortest path tree used here is equal to the shortest path
   857     ///tree used in \ref predNode().
   858     ///
   859     ///\pre Either \ref run() or \ref start() must be called before
   860     ///using this function.
   861     Arc predArc(Node v) const { return (*_pred)[v]; }
   862 
   863     ///Returns the 'previous node' of the shortest path tree for a node.
   864 
   865     ///This function returns the 'previous node' of the shortest path
   866     ///tree for the node \c v, i.e. it returns the last but one node
   867     ///from a shortest path from the root(s) to \c v. It is \c INVALID
   868     ///if \c v is not reachable from the root(s) or if \c v is a root.
   869     ///
   870     ///The shortest path tree used here is equal to the shortest path
   871     ///tree used in \ref predArc().
   872     ///
   873     ///\pre Either \ref run() or \ref start() must be called before
   874     ///using this function.
   875     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   876                                   G->source((*_pred)[v]); }
   877 
   878     ///\brief Returns a const reference to the node map that stores the
   879     ///distances of the nodes.
   880     ///
   881     ///Returns a const reference to the node map that stores the distances
   882     ///of the nodes calculated by the algorithm.
   883     ///
   884     ///\pre Either \ref run() or \ref init()
   885     ///must be called before using this function.
   886     const DistMap &distMap() const { return *_dist;}
   887 
   888     ///\brief Returns a const reference to the node map that stores the
   889     ///predecessor arcs.
   890     ///
   891     ///Returns a const reference to the node map that stores the predecessor
   892     ///arcs, which form the shortest path tree.
   893     ///
   894     ///\pre Either \ref run() or \ref init()
   895     ///must be called before using this function.
   896     const PredMap &predMap() const { return *_pred;}
   897 
   898     ///Checks if a node is reachable from the root(s).
   899 
   900     ///Returns \c true if \c v is reachable from the root(s).
   901     ///\pre Either \ref run() or \ref start()
   902     ///must be called before using this function.
   903     bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
   904                                         Heap::PRE_HEAP; }
   905 
   906     ///Checks if a node is processed.
   907 
   908     ///Returns \c true if \c v is processed, i.e. the shortest
   909     ///path to \c v has already found.
   910     ///\pre Either \ref run() or \ref init()
   911     ///must be called before using this function.
   912     bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
   913                                           Heap::POST_HEAP; }
   914 
   915     ///The current distance of a node from the root(s).
   916 
   917     ///Returns the current distance of a node from the root(s).
   918     ///It may be decreased in the following processes.
   919     ///\pre Either \ref run() or \ref init()
   920     ///must be called before using this function and
   921     ///node \c v must be reached but not necessarily processed.
   922     Value currentDist(Node v) const {
   923       return processed(v) ? (*_dist)[v] : (*_heap)[v];
   924     }
   925 
   926     ///@}
   927   };
   928 
   929 
   930   ///Default traits class of dijkstra() function.
   931 
   932   ///Default traits class of dijkstra() function.
   933   ///\tparam GR The type of the digraph.
   934   ///\tparam LM The type of the length map.
   935   template<class GR, class LM>
   936   struct DijkstraWizardDefaultTraits
   937   {
   938     ///The type of the digraph the algorithm runs on.
   939     typedef GR Digraph;
   940     ///The type of the map that stores the arc lengths.
   941 
   942     ///The type of the map that stores the arc lengths.
   943     ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
   944     typedef LM LengthMap;
   945     ///The type of the length of the arcs.
   946     typedef typename LM::Value Value;
   947 
   948     /// Operation traits for Dijkstra algorithm.
   949 
   950     /// This class defines the operations that are used in the algorithm.
   951     /// \see DijkstraDefaultOperationTraits
   952     typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
   953 
   954     /// The cross reference type used by the heap.
   955 
   956     /// The cross reference type used by the heap.
   957     /// Usually it is \c Digraph::NodeMap<int>.
   958     typedef typename Digraph::template NodeMap<int> HeapCrossRef;
   959     ///Instantiates a \ref HeapCrossRef.
   960 
   961     ///This function instantiates a \ref HeapCrossRef.
   962     /// \param g is the digraph, to which we would like to define the
   963     /// HeapCrossRef.
   964     static HeapCrossRef *createHeapCrossRef(const Digraph &g)
   965     {
   966       return new HeapCrossRef(g);
   967     }
   968 
   969     ///The heap type used by the Dijkstra algorithm.
   970 
   971     ///The heap type used by the Dijkstra algorithm.
   972     ///
   973     ///\sa BinHeap
   974     ///\sa Dijkstra
   975     typedef BinHeap<Value, typename Digraph::template NodeMap<int>,
   976                     std::less<Value> > Heap;
   977 
   978     ///Instantiates a \ref Heap.
   979 
   980     ///This function instantiates a \ref Heap.
   981     /// \param r is the HeapCrossRef which is used.
   982     static Heap *createHeap(HeapCrossRef& r)
   983     {
   984       return new Heap(r);
   985     }
   986 
   987     ///\brief The type of the map that stores the predecessor
   988     ///arcs of the shortest paths.
   989     ///
   990     ///The type of the map that stores the predecessor
   991     ///arcs of the shortest paths.
   992     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   993     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   994     ///Instantiates a \ref PredMap.
   995 
   996     ///This function instantiates a \ref PredMap.
   997     ///\param g is the digraph, to which we would like to define the
   998     ///\ref PredMap.
   999     static PredMap *createPredMap(const Digraph &g)
  1000     {
  1001       return new PredMap(g);
  1002     }
  1003 
  1004     ///The type of the map that indicates which nodes are processed.
  1005 
  1006     ///The type of the map that indicates which nodes are processed.
  1007     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
  1008     ///By default it is a NullMap.
  1009     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
  1010     ///Instantiates a \ref ProcessedMap.
  1011 
  1012     ///This function instantiates a \ref ProcessedMap.
  1013     ///\param g is the digraph, to which
  1014     ///we would like to define the \ref ProcessedMap.
  1015 #ifdef DOXYGEN
  1016     static ProcessedMap *createProcessedMap(const Digraph &g)
  1017 #else
  1018     static ProcessedMap *createProcessedMap(const Digraph &)
  1019 #endif
  1020     {
  1021       return new ProcessedMap();
  1022     }
  1023 
  1024     ///The type of the map that stores the distances of the nodes.
  1025 
  1026     ///The type of the map that stores the distances of the nodes.
  1027     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
  1028     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
  1029     ///Instantiates a \ref DistMap.
  1030 
  1031     ///This function instantiates a \ref DistMap.
  1032     ///\param g is the digraph, to which we would like to define
  1033     ///the \ref DistMap
  1034     static DistMap *createDistMap(const Digraph &g)
  1035     {
  1036       return new DistMap(g);
  1037     }
  1038 
  1039     ///The type of the shortest paths.
  1040 
  1041     ///The type of the shortest paths.
  1042     ///It must meet the \ref concepts::Path "Path" concept.
  1043     typedef lemon::Path<Digraph> Path;
  1044   };
  1045 
  1046   /// Default traits class used by \ref DijkstraWizard
  1047 
  1048   /// To make it easier to use Dijkstra algorithm
  1049   /// we have created a wizard class.
  1050   /// This \ref DijkstraWizard class needs default traits,
  1051   /// as well as the \ref Dijkstra class.
  1052   /// The \ref DijkstraWizardBase is a class to be the default traits of the
  1053   /// \ref DijkstraWizard class.
  1054   template<class GR,class LM>
  1055   class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
  1056   {
  1057     typedef DijkstraWizardDefaultTraits<GR,LM> Base;
  1058   protected:
  1059     //The type of the nodes in the digraph.
  1060     typedef typename Base::Digraph::Node Node;
  1061 
  1062     //Pointer to the digraph the algorithm runs on.
  1063     void *_g;
  1064     //Pointer to the length map.
  1065     void *_length;
  1066     //Pointer to the map of processed nodes.
  1067     void *_processed;
  1068     //Pointer to the map of predecessors arcs.
  1069     void *_pred;
  1070     //Pointer to the map of distances.
  1071     void *_dist;
  1072     //Pointer to the shortest path to the target node.
  1073     void *_path;
  1074     //Pointer to the distance of the target node.
  1075     void *_di;
  1076 
  1077   public:
  1078     /// Constructor.
  1079 
  1080     /// This constructor does not require parameters, therefore it initiates
  1081     /// all of the attributes to \c 0.
  1082     DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
  1083                            _dist(0), _path(0), _di(0) {}
  1084 
  1085     /// Constructor.
  1086 
  1087     /// This constructor requires two parameters,
  1088     /// others are initiated to \c 0.
  1089     /// \param g The digraph the algorithm runs on.
  1090     /// \param l The length map.
  1091     DijkstraWizardBase(const GR &g,const LM &l) :
  1092       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
  1093       _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
  1094       _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
  1095 
  1096   };
  1097 
  1098   /// Auxiliary class for the function-type interface of Dijkstra algorithm.
  1099 
  1100   /// This auxiliary class is created to implement the
  1101   /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
  1102   /// It does not have own \ref run() method, it uses the functions
  1103   /// and features of the plain \ref Dijkstra.
  1104   ///
  1105   /// This class should only be used through the \ref dijkstra() function,
  1106   /// which makes it easier to use the algorithm.
  1107   template<class TR>
  1108   class DijkstraWizard : public TR
  1109   {
  1110     typedef TR Base;
  1111 
  1112     ///The type of the digraph the algorithm runs on.
  1113     typedef typename TR::Digraph Digraph;
  1114 
  1115     typedef typename Digraph::Node Node;
  1116     typedef typename Digraph::NodeIt NodeIt;
  1117     typedef typename Digraph::Arc Arc;
  1118     typedef typename Digraph::OutArcIt OutArcIt;
  1119 
  1120     ///The type of the map that stores the arc lengths.
  1121     typedef typename TR::LengthMap LengthMap;
  1122     ///The type of the length of the arcs.
  1123     typedef typename LengthMap::Value Value;
  1124     ///\brief The type of the map that stores the predecessor
  1125     ///arcs of the shortest paths.
  1126     typedef typename TR::PredMap PredMap;
  1127     ///The type of the map that stores the distances of the nodes.
  1128     typedef typename TR::DistMap DistMap;
  1129     ///The type of the map that indicates which nodes are processed.
  1130     typedef typename TR::ProcessedMap ProcessedMap;
  1131     ///The type of the shortest paths
  1132     typedef typename TR::Path Path;
  1133     ///The heap type used by the dijkstra algorithm.
  1134     typedef typename TR::Heap Heap;
  1135 
  1136   public:
  1137 
  1138     /// Constructor.
  1139     DijkstraWizard() : TR() {}
  1140 
  1141     /// Constructor that requires parameters.
  1142 
  1143     /// Constructor that requires parameters.
  1144     /// These parameters will be the default values for the traits class.
  1145     /// \param g The digraph the algorithm runs on.
  1146     /// \param l The length map.
  1147     DijkstraWizard(const Digraph &g, const LengthMap &l) :
  1148       TR(g,l) {}
  1149 
  1150     ///Copy constructor
  1151     DijkstraWizard(const TR &b) : TR(b) {}
  1152 
  1153     ~DijkstraWizard() {}
  1154 
  1155     ///Runs Dijkstra algorithm from the given source node.
  1156 
  1157     ///This method runs %Dijkstra algorithm from the given source node
  1158     ///in order to compute the shortest path to each node.
  1159     void run(Node s)
  1160     {
  1161       if (s==INVALID) throw UninitializedParameter();
  1162       Dijkstra<Digraph,LengthMap,TR>
  1163         dijk(*reinterpret_cast<const Digraph*>(Base::_g),
  1164              *reinterpret_cast<const LengthMap*>(Base::_length));
  1165       if (Base::_pred)
  1166         dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
  1167       if (Base::_dist)
  1168         dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
  1169       if (Base::_processed)
  1170         dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
  1171       dijk.run(s);
  1172     }
  1173 
  1174     ///Finds the shortest path between \c s and \c t.
  1175 
  1176     ///This method runs the %Dijkstra algorithm from node \c s
  1177     ///in order to compute the shortest path to node \c t
  1178     ///(it stops searching when \c t is processed).
  1179     ///
  1180     ///\return \c true if \c t is reachable form \c s.
  1181     bool run(Node s, Node t)
  1182     {
  1183       if (s==INVALID || t==INVALID) throw UninitializedParameter();
  1184       Dijkstra<Digraph,LengthMap,TR>
  1185         dijk(*reinterpret_cast<const Digraph*>(Base::_g),
  1186              *reinterpret_cast<const LengthMap*>(Base::_length));
  1187       if (Base::_pred)
  1188         dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
  1189       if (Base::_dist)
  1190         dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
  1191       if (Base::_processed)
  1192         dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
  1193       dijk.run(s,t);
  1194       if (Base::_path)
  1195         *reinterpret_cast<Path*>(Base::_path) = dijk.path(t);
  1196       if (Base::_di)
  1197         *reinterpret_cast<Value*>(Base::_di) = dijk.dist(t);
  1198       return dijk.reached(t);
  1199     }
  1200 
  1201     template<class T>
  1202     struct SetPredMapBase : public Base {
  1203       typedef T PredMap;
  1204       static PredMap *createPredMap(const Digraph &) { return 0; };
  1205       SetPredMapBase(const TR &b) : TR(b) {}
  1206     };
  1207     ///\brief \ref named-func-param "Named parameter"
  1208     ///for setting \ref PredMap object.
  1209     ///
  1210     ///\ref named-func-param "Named parameter"
  1211     ///for setting \ref PredMap object.
  1212     template<class T>
  1213     DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
  1214     {
  1215       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1216       return DijkstraWizard<SetPredMapBase<T> >(*this);
  1217     }
  1218 
  1219     template<class T>
  1220     struct SetDistMapBase : public Base {
  1221       typedef T DistMap;
  1222       static DistMap *createDistMap(const Digraph &) { return 0; };
  1223       SetDistMapBase(const TR &b) : TR(b) {}
  1224     };
  1225     ///\brief \ref named-func-param "Named parameter"
  1226     ///for setting \ref DistMap object.
  1227     ///
  1228     ///\ref named-func-param "Named parameter"
  1229     ///for setting \ref DistMap object.
  1230     template<class T>
  1231     DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
  1232     {
  1233       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
  1234       return DijkstraWizard<SetDistMapBase<T> >(*this);
  1235     }
  1236 
  1237     template<class T>
  1238     struct SetProcessedMapBase : public Base {
  1239       typedef T ProcessedMap;
  1240       static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  1241       SetProcessedMapBase(const TR &b) : TR(b) {}
  1242     };
  1243     ///\brief \ref named-func-param "Named parameter"
  1244     ///for setting \ref ProcessedMap object.
  1245     ///
  1246     /// \ref named-func-param "Named parameter"
  1247     ///for setting \ref ProcessedMap object.
  1248     template<class T>
  1249     DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
  1250     {
  1251       Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
  1252       return DijkstraWizard<SetProcessedMapBase<T> >(*this);
  1253     }
  1254 
  1255     template<class T>
  1256     struct SetPathBase : public Base {
  1257       typedef T Path;
  1258       SetPathBase(const TR &b) : TR(b) {}
  1259     };
  1260     ///\brief \ref named-func-param "Named parameter"
  1261     ///for getting the shortest path to the target node.
  1262     ///
  1263     ///\ref named-func-param "Named parameter"
  1264     ///for getting the shortest path to the target node.
  1265     template<class T>
  1266     DijkstraWizard<SetPathBase<T> > path(const T &t)
  1267     {
  1268       Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
  1269       return DijkstraWizard<SetPathBase<T> >(*this);
  1270     }
  1271 
  1272     ///\brief \ref named-func-param "Named parameter"
  1273     ///for getting the distance of the target node.
  1274     ///
  1275     ///\ref named-func-param "Named parameter"
  1276     ///for getting the distance of the target node.
  1277     DijkstraWizard dist(const Value &d)
  1278     {
  1279       Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
  1280       return *this;
  1281     }
  1282 
  1283   };
  1284 
  1285   ///Function-type interface for Dijkstra algorithm.
  1286 
  1287   /// \ingroup shortest_path
  1288   ///Function-type interface for Dijkstra algorithm.
  1289   ///
  1290   ///This function also has several \ref named-func-param "named parameters",
  1291   ///they are declared as the members of class \ref DijkstraWizard.
  1292   ///The following examples show how to use these parameters.
  1293   ///\code
  1294   ///  // Compute shortest path from node s to each node
  1295   ///  dijkstra(g,length).predMap(preds).distMap(dists).run(s);
  1296   ///
  1297   ///  // Compute shortest path from s to t
  1298   ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
  1299   ///\endcode
  1300   ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
  1301   ///to the end of the parameter list.
  1302   ///\sa DijkstraWizard
  1303   ///\sa Dijkstra
  1304   template<class GR, class LM>
  1305   DijkstraWizard<DijkstraWizardBase<GR,LM> >
  1306   dijkstra(const GR &digraph, const LM &length)
  1307   {
  1308     return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
  1309   }
  1310 
  1311 } //END OF NAMESPACE LEMON
  1312 
  1313 #endif