lemon/dijkstra.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 18:59:15 +0200
changeset 608 6ac5d9ae1d3d
parent 440 88ed40ad0d4f
child 559 c5fd2d996909
permissions -rw-r--r--
Support real types + numerical stability fix in NS (#254)

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