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