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