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