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