lemon/dijkstra.h
author Alpar Juttner <alpar@cs.elte.hu>
Sun, 21 Sep 2008 06:13:05 +0100
changeset 267 1eb606fe5591
parent 257 8d76a7bf9961
parent 251 a1ffc9099c25
child 278 931190050520
child 280 e7f8647ce760
permissions -rw-r--r--
Port named-param.dox from svn -r3504
     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 SetPredMapTraits : 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 SetPredMap
   348       : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
   349       typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
   350     };
   351 
   352     template <class T>
   353     struct SetDistMapTraits : 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 SetDistMap
   367       : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
   368       typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
   369     };
   370 
   371     template <class T>
   372     struct SetProcessedMapTraits : 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 SetProcessedMap
   386       : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
   387       typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
   388     };
   389 
   390     struct SetStandardProcessedMapTraits : 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     struct SetStandardProcessedMap
   404       : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
   405       typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >
   406       Create;
   407     };
   408 
   409     template <class H, class CR>
   410     struct SetHeapTraits : public Traits {
   411       typedef CR HeapCrossRef;
   412       typedef H Heap;
   413       static HeapCrossRef *createHeapCrossRef(const Digraph &) {
   414         throw UninitializedParameter();
   415       }
   416       static Heap *createHeap(HeapCrossRef &)
   417       {
   418         throw UninitializedParameter();
   419       }
   420     };
   421     ///\brief \ref named-templ-param "Named parameter" for setting
   422     ///heap and cross reference type
   423     ///
   424     ///\ref named-templ-param "Named parameter" for setting heap and cross
   425     ///reference type.
   426     template <class H, class CR = typename Digraph::template NodeMap<int> >
   427     struct SetHeap
   428       : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
   429       typedef Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > Create;
   430     };
   431 
   432     template <class H, class CR>
   433     struct SetStandardHeapTraits : public Traits {
   434       typedef CR HeapCrossRef;
   435       typedef H Heap;
   436       static HeapCrossRef *createHeapCrossRef(const Digraph &G) {
   437         return new HeapCrossRef(G);
   438       }
   439       static Heap *createHeap(HeapCrossRef &R)
   440       {
   441         return new Heap(R);
   442       }
   443     };
   444     ///\brief \ref named-templ-param "Named parameter" for setting
   445     ///heap and cross reference type with automatic allocation
   446     ///
   447     ///\ref named-templ-param "Named parameter" for setting heap and cross
   448     ///reference type. It can allocate the heap and the cross reference
   449     ///object if the cross reference's constructor waits for the digraph as
   450     ///parameter and the heap's constructor waits for the cross reference.
   451     template <class H, class CR = typename Digraph::template NodeMap<int> >
   452     struct SetStandardHeap
   453       : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
   454       typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> >
   455       Create;
   456     };
   457 
   458     template <class T>
   459     struct SetOperationTraitsTraits : public Traits {
   460       typedef T OperationTraits;
   461     };
   462 
   463     /// \brief \ref named-templ-param "Named parameter" for setting
   464     ///\ref OperationTraits type
   465     ///
   466     ///\ref named-templ-param "Named parameter" for setting
   467     ///\ref OperationTraits type.
   468     template <class T>
   469     struct SetOperationTraits
   470       : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
   471       typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >
   472       Create;
   473     };
   474 
   475     ///@}
   476 
   477   protected:
   478 
   479     Dijkstra() {}
   480 
   481   public:
   482 
   483     ///Constructor.
   484 
   485     ///Constructor.
   486     ///\param _g The digraph the algorithm runs on.
   487     ///\param _length The length map used by the algorithm.
   488     Dijkstra(const Digraph& _g, const LengthMap& _length) :
   489       G(&_g), length(&_length),
   490       _pred(NULL), local_pred(false),
   491       _dist(NULL), local_dist(false),
   492       _processed(NULL), local_processed(false),
   493       _heap_cross_ref(NULL), local_heap_cross_ref(false),
   494       _heap(NULL), local_heap(false)
   495     { }
   496 
   497     ///Destructor.
   498     ~Dijkstra()
   499     {
   500       if(local_pred) delete _pred;
   501       if(local_dist) delete _dist;
   502       if(local_processed) delete _processed;
   503       if(local_heap_cross_ref) delete _heap_cross_ref;
   504       if(local_heap) delete _heap;
   505     }
   506 
   507     ///Sets the length map.
   508 
   509     ///Sets the length map.
   510     ///\return <tt> (*this) </tt>
   511     Dijkstra &lengthMap(const LengthMap &m)
   512     {
   513       length = &m;
   514       return *this;
   515     }
   516 
   517     ///Sets the map that stores the predecessor arcs.
   518 
   519     ///Sets the map that stores the predecessor arcs.
   520     ///If you don't use this function before calling \ref run(),
   521     ///it will allocate one. The destructor deallocates this
   522     ///automatically allocated map, of course.
   523     ///\return <tt> (*this) </tt>
   524     Dijkstra &predMap(PredMap &m)
   525     {
   526       if(local_pred) {
   527         delete _pred;
   528         local_pred=false;
   529       }
   530       _pred = &m;
   531       return *this;
   532     }
   533 
   534     ///Sets the map that indicates which nodes are processed.
   535 
   536     ///Sets the map that indicates which nodes are processed.
   537     ///If you don't use this function before calling \ref run(),
   538     ///it will allocate one. The destructor deallocates this
   539     ///automatically allocated map, of course.
   540     ///\return <tt> (*this) </tt>
   541     Dijkstra &processedMap(ProcessedMap &m)
   542     {
   543       if(local_processed) {
   544         delete _processed;
   545         local_processed=false;
   546       }
   547       _processed = &m;
   548       return *this;
   549     }
   550 
   551     ///Sets the map that stores the distances of the nodes.
   552 
   553     ///Sets the map that stores the distances of the nodes calculated by the
   554     ///algorithm.
   555     ///If you don't use this function before calling \ref run(),
   556     ///it will allocate one. The destructor deallocates this
   557     ///automatically allocated map, of course.
   558     ///\return <tt> (*this) </tt>
   559     Dijkstra &distMap(DistMap &m)
   560     {
   561       if(local_dist) {
   562         delete _dist;
   563         local_dist=false;
   564       }
   565       _dist = &m;
   566       return *this;
   567     }
   568 
   569     ///Sets the heap and the cross reference used by algorithm.
   570 
   571     ///Sets the heap and the cross reference used by algorithm.
   572     ///If you don't use this function before calling \ref run(),
   573     ///it will allocate one. The destructor deallocates this
   574     ///automatically allocated heap and cross reference, of course.
   575     ///\return <tt> (*this) </tt>
   576     Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
   577     {
   578       if(local_heap_cross_ref) {
   579         delete _heap_cross_ref;
   580         local_heap_cross_ref=false;
   581       }
   582       _heap_cross_ref = &cr;
   583       if(local_heap) {
   584         delete _heap;
   585         local_heap=false;
   586       }
   587       _heap = &hp;
   588       return *this;
   589     }
   590 
   591   private:
   592 
   593     void finalizeNodeData(Node v,Value dst)
   594     {
   595       _processed->set(v,true);
   596       _dist->set(v, dst);
   597     }
   598 
   599   public:
   600 
   601     ///\name Execution control
   602     ///The simplest way to execute the algorithm is to use one of the
   603     ///member functions called \ref lemon::Dijkstra::run() "run()".
   604     ///\n
   605     ///If you need more control on the execution, first you must call
   606     ///\ref lemon::Dijkstra::init() "init()", then you can add several
   607     ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
   608     ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
   609     ///actual path computation.
   610 
   611     ///@{
   612 
   613     ///Initializes the internal data structures.
   614 
   615     ///Initializes the internal data structures.
   616     ///
   617     void init()
   618     {
   619       create_maps();
   620       _heap->clear();
   621       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
   622         _pred->set(u,INVALID);
   623         _processed->set(u,false);
   624         _heap_cross_ref->set(u,Heap::PRE_HEAP);
   625       }
   626     }
   627 
   628     ///Adds a new source node.
   629 
   630     ///Adds a new source node to the priority heap.
   631     ///The optional second parameter is the initial distance of the node.
   632     ///
   633     ///The function checks if the node has already been added to the heap and
   634     ///it is pushed to the heap only if either it was not in the heap
   635     ///or the shortest path found till then is shorter than \c dst.
   636     void addSource(Node s,Value dst=OperationTraits::zero())
   637     {
   638       if(_heap->state(s) != Heap::IN_HEAP) {
   639         _heap->push(s,dst);
   640       } else if(OperationTraits::less((*_heap)[s], dst)) {
   641         _heap->set(s,dst);
   642         _pred->set(s,INVALID);
   643       }
   644     }
   645 
   646     ///Processes the next node in the priority heap
   647 
   648     ///Processes the next node in the priority heap.
   649     ///
   650     ///\return The processed node.
   651     ///
   652     ///\warning The priority heap must not be empty.
   653     Node processNextNode()
   654     {
   655       Node v=_heap->top();
   656       Value oldvalue=_heap->prio();
   657       _heap->pop();
   658       finalizeNodeData(v,oldvalue);
   659 
   660       for(OutArcIt e(*G,v); e!=INVALID; ++e) {
   661         Node w=G->target(e);
   662         switch(_heap->state(w)) {
   663         case Heap::PRE_HEAP:
   664           _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
   665           _pred->set(w,e);
   666           break;
   667         case Heap::IN_HEAP:
   668           {
   669             Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
   670             if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
   671               _heap->decrease(w, newvalue);
   672               _pred->set(w,e);
   673             }
   674           }
   675           break;
   676         case Heap::POST_HEAP:
   677           break;
   678         }
   679       }
   680       return v;
   681     }
   682 
   683     ///The next node to be processed.
   684 
   685     ///Returns the next node to be processed or \c INVALID if the
   686     ///priority heap is empty.
   687     Node nextNode() const
   688     {
   689       return !_heap->empty()?_heap->top():INVALID;
   690     }
   691 
   692     ///\brief Returns \c false if there are nodes
   693     ///to be processed.
   694     ///
   695     ///Returns \c false if there are nodes
   696     ///to be processed in the priority heap.
   697     bool emptyQueue() const { return _heap->empty(); }
   698 
   699     ///Returns the number of the nodes to be processed in the priority heap
   700 
   701     ///Returns the number of the nodes to be processed in the priority heap.
   702     ///
   703     int queueSize() const { return _heap->size(); }
   704 
   705     ///Executes the algorithm.
   706 
   707     ///Executes the algorithm.
   708     ///
   709     ///This method runs the %Dijkstra algorithm from the root node(s)
   710     ///in order to compute the shortest path to each node.
   711     ///
   712     ///The algorithm computes
   713     ///- the shortest path tree (forest),
   714     ///- the distance of each node from the root(s).
   715     ///
   716     ///\pre init() must be called and at least one root node should be
   717     ///added with addSource() before using this function.
   718     ///
   719     ///\note <tt>d.start()</tt> is just a shortcut of the following code.
   720     ///\code
   721     ///  while ( !d.emptyQueue() ) {
   722     ///    d.processNextNode();
   723     ///  }
   724     ///\endcode
   725     void start()
   726     {
   727       while ( !emptyQueue() ) processNextNode();
   728     }
   729 
   730     ///Executes the algorithm until the given target node is reached.
   731 
   732     ///Executes the algorithm until the given target node is reached.
   733     ///
   734     ///This method runs the %Dijkstra algorithm from the root node(s)
   735     ///in order to compute the shortest path to \c dest.
   736     ///
   737     ///The algorithm computes
   738     ///- the shortest path to \c dest,
   739     ///- the distance of \c dest from the root(s).
   740     ///
   741     ///\pre init() must be called and at least one root node should be
   742     ///added with addSource() before using this function.
   743     void start(Node dest)
   744     {
   745       while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
   746       if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
   747     }
   748 
   749     ///Executes the algorithm until a condition is met.
   750 
   751     ///Executes the algorithm until a condition is met.
   752     ///
   753     ///This method runs the %Dijkstra algorithm from the root node(s) in
   754     ///order to compute the shortest path to a node \c v with
   755     /// <tt>nm[v]</tt> true, if such a node can be found.
   756     ///
   757     ///\param nm A \c bool (or convertible) node map. The algorithm
   758     ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
   759     ///
   760     ///\return The reached node \c v with <tt>nm[v]</tt> true or
   761     ///\c INVALID if no such node was found.
   762     ///
   763     ///\pre init() must be called and at least one root node should be
   764     ///added with addSource() before using this function.
   765     template<class NodeBoolMap>
   766     Node start(const NodeBoolMap &nm)
   767     {
   768       while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
   769       if ( _heap->empty() ) return INVALID;
   770       finalizeNodeData(_heap->top(),_heap->prio());
   771       return _heap->top();
   772     }
   773 
   774     ///Runs the algorithm from the given node.
   775 
   776     ///This method runs the %Dijkstra algorithm from node \c s
   777     ///in order to compute the shortest path to each node.
   778     ///
   779     ///The algorithm computes
   780     ///- the shortest path tree,
   781     ///- the distance of each node from the root.
   782     ///
   783     ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
   784     ///\code
   785     ///  d.init();
   786     ///  d.addSource(s);
   787     ///  d.start();
   788     ///\endcode
   789     void run(Node s) {
   790       init();
   791       addSource(s);
   792       start();
   793     }
   794 
   795     ///Finds the shortest path between \c s and \c t.
   796 
   797     ///This method runs the %Dijkstra algorithm from node \c s
   798     ///in order to compute the shortest path to \c t.
   799     ///
   800     ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
   801     ///if \c t is reachable form \c s, \c 0 otherwise.
   802     ///
   803     ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
   804     ///shortcut of the following code.
   805     ///\code
   806     ///  d.init();
   807     ///  d.addSource(s);
   808     ///  d.start(t);
   809     ///\endcode
   810     Value run(Node s,Node t) {
   811       init();
   812       addSource(s);
   813       start(t);
   814       return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
   815     }
   816 
   817     ///@}
   818 
   819     ///\name Query Functions
   820     ///The result of the %Dijkstra algorithm can be obtained using these
   821     ///functions.\n
   822     ///Either \ref lemon::Dijkstra::run() "run()" or
   823     ///\ref lemon::Dijkstra::start() "start()" must be called before
   824     ///using them.
   825 
   826     ///@{
   827 
   828     ///The shortest path to a node.
   829 
   830     ///Returns the shortest path to a node.
   831     ///
   832     ///\warning \c t should be reachable from the root(s).
   833     ///
   834     ///\pre Either \ref run() or \ref start() must be called before
   835     ///using this function.
   836     Path path(Node t) const { return Path(*G, *_pred, t); }
   837 
   838     ///The distance of a node from the root(s).
   839 
   840     ///Returns the distance of a node from the root(s).
   841     ///
   842     ///\warning If node \c v is not reachable from the root(s), then
   843     ///the return value of this function is undefined.
   844     ///
   845     ///\pre Either \ref run() or \ref start() must be called before
   846     ///using this function.
   847     Value dist(Node v) const { return (*_dist)[v]; }
   848 
   849     ///Returns the 'previous arc' of the shortest path tree for a node.
   850 
   851     ///This function returns the 'previous arc' of the shortest path
   852     ///tree for the node \c v, i.e. it returns the last arc of a
   853     ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
   854     ///is not reachable from the root(s) or if \c v is a root.
   855     ///
   856     ///The shortest path tree used here is equal to the shortest path
   857     ///tree used in \ref predNode().
   858     ///
   859     ///\pre Either \ref run() or \ref start() must be called before
   860     ///using this function.
   861     Arc predArc(Node v) const { return (*_pred)[v]; }
   862 
   863     ///Returns the 'previous node' of the shortest path tree for a node.
   864 
   865     ///This function returns the 'previous node' of the shortest path
   866     ///tree for the node \c v, i.e. it returns the last but one node
   867     ///from a shortest path from the root(s) to \c v. It is \c INVALID
   868     ///if \c v is not reachable from the root(s) or if \c v is a root.
   869     ///
   870     ///The shortest path tree used here is equal to the shortest path
   871     ///tree used in \ref predArc().
   872     ///
   873     ///\pre Either \ref run() or \ref start() must be called before
   874     ///using this function.
   875     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   876                                   G->source((*_pred)[v]); }
   877 
   878     ///\brief Returns a const reference to the node map that stores the
   879     ///distances of the nodes.
   880     ///
   881     ///Returns a const reference to the node map that stores the distances
   882     ///of the nodes calculated by the algorithm.
   883     ///
   884     ///\pre Either \ref run() or \ref init()
   885     ///must be called before using this function.
   886     const DistMap &distMap() const { return *_dist;}
   887 
   888     ///\brief Returns a const reference to the node map that stores the
   889     ///predecessor arcs.
   890     ///
   891     ///Returns a const reference to the node map that stores the predecessor
   892     ///arcs, which form the shortest path tree.
   893     ///
   894     ///\pre Either \ref run() or \ref init()
   895     ///must be called before using this function.
   896     const PredMap &predMap() const { return *_pred;}
   897 
   898     ///Checks if a node is reachable from the root(s).
   899 
   900     ///Returns \c true if \c v is reachable from the root(s).
   901     ///\pre Either \ref run() or \ref start()
   902     ///must be called before using this function.
   903     bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
   904                                         Heap::PRE_HEAP; }
   905 
   906     ///Checks if a node is processed.
   907 
   908     ///Returns \c true if \c v is processed, i.e. the shortest
   909     ///path to \c v has already found.
   910     ///\pre Either \ref run() or \ref start()
   911     ///must be called before using this function.
   912     bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
   913                                           Heap::POST_HEAP; }
   914 
   915     ///The current distance of a node from the root(s).
   916 
   917     ///Returns the current distance of a node from the root(s).
   918     ///It may be decreased in the following processes.
   919     ///\pre \c v should be reached but not processed.
   920     Value currentDist(Node v) const { return (*_heap)[v]; }
   921 
   922     ///@}
   923   };
   924 
   925 
   926   ///Default traits class of dijkstra() function.
   927 
   928   ///Default traits class of dijkstra() function.
   929   ///\tparam GR The type of the digraph.
   930   ///\tparam LM The type of the length map.
   931   template<class GR, class LM>
   932   struct DijkstraWizardDefaultTraits
   933   {
   934     ///The type of the digraph the algorithm runs on.
   935     typedef GR Digraph;
   936     ///The type of the map that stores the arc lengths.
   937 
   938     ///The type of the map that stores the arc lengths.
   939     ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
   940     typedef LM LengthMap;
   941     ///The type of the length of the arcs.
   942     typedef typename LM::Value Value;
   943 
   944     /// Operation traits for Dijkstra algorithm.
   945 
   946     /// This class defines the operations that are used in the algorithm.
   947     /// \see DijkstraDefaultOperationTraits
   948     typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
   949 
   950     /// The cross reference type used by the heap.
   951 
   952     /// The cross reference type used by the heap.
   953     /// Usually it is \c Digraph::NodeMap<int>.
   954     typedef typename Digraph::template NodeMap<int> HeapCrossRef;
   955     ///Instantiates a \ref HeapCrossRef.
   956 
   957     ///This function instantiates a \ref HeapCrossRef.
   958     /// \param g is the digraph, to which we would like to define the
   959     /// HeapCrossRef.
   960     /// \todo The digraph alone may be insufficient for the initialization
   961     static HeapCrossRef *createHeapCrossRef(const Digraph &g)
   962     {
   963       return new HeapCrossRef(g);
   964     }
   965 
   966     ///The heap type used by the Dijkstra algorithm.
   967 
   968     ///The heap type used by the Dijkstra algorithm.
   969     ///
   970     ///\sa BinHeap
   971     ///\sa Dijkstra
   972     typedef BinHeap<Value, typename Digraph::template NodeMap<int>,
   973                     std::less<Value> > Heap;
   974 
   975     ///Instantiates a \ref Heap.
   976 
   977     ///This function instantiates a \ref Heap.
   978     /// \param r is the HeapCrossRef which is used.
   979     static Heap *createHeap(HeapCrossRef& r)
   980     {
   981       return new Heap(r);
   982     }
   983 
   984     ///\brief The type of the map that stores the predecessor
   985     ///arcs of the shortest paths.
   986     ///
   987     ///The type of the map that stores the predecessor
   988     ///arcs of the shortest paths.
   989     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   990     typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;
   991     ///Instantiates a \ref PredMap.
   992 
   993     ///This function instantiates a \ref PredMap.
   994     ///\param g is the digraph, to which we would like to define the
   995     ///\ref PredMap.
   996     ///\todo The digraph alone may be insufficient to initialize
   997 #ifdef DOXYGEN
   998     static PredMap *createPredMap(const Digraph &g)
   999 #else
  1000     static PredMap *createPredMap(const Digraph &)
  1001 #endif
  1002     {
  1003       return new PredMap();
  1004     }
  1005 
  1006     ///The type of the map that indicates which nodes are processed.
  1007 
  1008     ///The type of the map that indicates which nodes are processed.
  1009     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
  1010     ///By default it is a NullMap.
  1011     ///\todo If it is set to a real map,
  1012     ///Dijkstra::processed() should read this.
  1013     ///\todo named parameter to set this type, function to read and write.
  1014     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
  1015     ///Instantiates a \ref ProcessedMap.
  1016 
  1017     ///This function instantiates a \ref ProcessedMap.
  1018     ///\param g is the digraph, to which
  1019     ///we would like to define the \ref ProcessedMap.
  1020 #ifdef DOXYGEN
  1021     static ProcessedMap *createProcessedMap(const Digraph &g)
  1022 #else
  1023     static ProcessedMap *createProcessedMap(const Digraph &)
  1024 #endif
  1025     {
  1026       return new ProcessedMap();
  1027     }
  1028 
  1029     ///The type of the map that stores the distances of the nodes.
  1030 
  1031     ///The type of the map that stores the distances of the nodes.
  1032     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
  1033     typedef NullMap<typename Digraph::Node,Value> DistMap;
  1034     ///Instantiates a \ref DistMap.
  1035 
  1036     ///This function instantiates a \ref DistMap.
  1037     ///\param g is the digraph, to which we would like to define
  1038     ///the \ref DistMap
  1039 #ifdef DOXYGEN
  1040     static DistMap *createDistMap(const Digraph &g)
  1041 #else
  1042     static DistMap *createDistMap(const Digraph &)
  1043 #endif
  1044     {
  1045       return new DistMap();
  1046     }
  1047   };
  1048 
  1049   /// Default traits class used by \ref DijkstraWizard
  1050 
  1051   /// To make it easier to use Dijkstra algorithm
  1052   /// we have created a wizard class.
  1053   /// This \ref DijkstraWizard class needs default traits,
  1054   /// as well as the \ref Dijkstra class.
  1055   /// The \ref DijkstraWizardBase is a class to be the default traits of the
  1056   /// \ref DijkstraWizard class.
  1057   /// \todo More named parameters are required...
  1058   template<class GR,class LM>
  1059   class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
  1060   {
  1061     typedef DijkstraWizardDefaultTraits<GR,LM> Base;
  1062   protected:
  1063     //The type of the nodes in the digraph.
  1064     typedef typename Base::Digraph::Node Node;
  1065 
  1066     //Pointer to the digraph the algorithm runs on.
  1067     void *_g;
  1068     //Pointer to the length map
  1069     void *_length;
  1070     //Pointer to the map of processed nodes.
  1071     void *_processed;
  1072     //Pointer to the map of predecessors arcs.
  1073     void *_pred;
  1074     //Pointer to the map of distances.
  1075     void *_dist;
  1076     //Pointer to the source node.
  1077     Node _source;
  1078 
  1079   public:
  1080     /// Constructor.
  1081 
  1082     /// This constructor does not require parameters, therefore it initiates
  1083     /// all of the attributes to default values (0, INVALID).
  1084     DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
  1085                            _dist(0), _source(INVALID) {}
  1086 
  1087     /// Constructor.
  1088 
  1089     /// This constructor requires some parameters,
  1090     /// listed in the parameters list.
  1091     /// Others are initiated to 0.
  1092     /// \param g The digraph the algorithm runs on.
  1093     /// \param l The length map.
  1094     /// \param s The source node.
  1095     DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
  1096       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
  1097       _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
  1098       _processed(0), _pred(0), _dist(0), _source(s) {}
  1099 
  1100   };
  1101 
  1102   /// Auxiliary class for the function type interface of Dijkstra algorithm.
  1103 
  1104   /// This auxiliary class is created to implement the function type
  1105   /// interface of \ref Dijkstra algorithm. It uses the functions and features
  1106   /// of the plain \ref Dijkstra, but it is much simpler to use it.
  1107   /// It should only be used through the \ref dijkstra() function, which makes
  1108   /// it easier to use the algorithm.
  1109   ///
  1110   /// Simplicity means that the way to change the types defined
  1111   /// in the traits class is based on functions that returns the new class
  1112   /// and not on templatable built-in classes.
  1113   /// When using the plain \ref Dijkstra
  1114   /// the new class with the modified type comes from
  1115   /// the original class by using the ::
  1116   /// operator. In the case of \ref DijkstraWizard only
  1117   /// a function have to be called, and it will
  1118   /// return the needed class.
  1119   ///
  1120   /// It does not have own \ref run() method. When its \ref run() method
  1121   /// is called, it initiates a plain \ref Dijkstra object, and calls the
  1122   /// \ref Dijkstra::run() method of it.
  1123   template<class TR>
  1124   class DijkstraWizard : public TR
  1125   {
  1126     typedef TR Base;
  1127 
  1128     ///The type of the digraph the algorithm runs on.
  1129     typedef typename TR::Digraph Digraph;
  1130 
  1131     typedef typename Digraph::Node Node;
  1132     typedef typename Digraph::NodeIt NodeIt;
  1133     typedef typename Digraph::Arc Arc;
  1134     typedef typename Digraph::OutArcIt OutArcIt;
  1135 
  1136     ///The type of the map that stores the arc lengths.
  1137     typedef typename TR::LengthMap LengthMap;
  1138     ///The type of the length of the arcs.
  1139     typedef typename LengthMap::Value Value;
  1140     ///\brief The type of the map that stores the predecessor
  1141     ///arcs of the shortest paths.
  1142     typedef typename TR::PredMap PredMap;
  1143     ///The type of the map that stores the distances of the nodes.
  1144     typedef typename TR::DistMap DistMap;
  1145     ///The type of the map that indicates which nodes are processed.
  1146     typedef typename TR::ProcessedMap ProcessedMap;
  1147     ///The heap type used by the dijkstra algorithm.
  1148     typedef typename TR::Heap Heap;
  1149 
  1150   public:
  1151 
  1152     /// Constructor.
  1153     DijkstraWizard() : TR() {}
  1154 
  1155     /// Constructor that requires parameters.
  1156 
  1157     /// Constructor that requires parameters.
  1158     /// These parameters will be the default values for the traits class.
  1159     DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) :
  1160       TR(g,l,s) {}
  1161 
  1162     ///Copy constructor
  1163     DijkstraWizard(const TR &b) : TR(b) {}
  1164 
  1165     ~DijkstraWizard() {}
  1166 
  1167     ///Runs Dijkstra algorithm from a source node.
  1168 
  1169     ///Runs Dijkstra algorithm from a source node.
  1170     ///The node can be given with the \ref source() function.
  1171     void run()
  1172     {
  1173       if(Base::_source==INVALID) throw UninitializedParameter();
  1174       Dijkstra<Digraph,LengthMap,TR>
  1175         dij(*reinterpret_cast<const Digraph*>(Base::_g),
  1176             *reinterpret_cast<const LengthMap*>(Base::_length));
  1177       if(Base::_processed)
  1178         dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
  1179       if(Base::_pred)
  1180         dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
  1181       if(Base::_dist)
  1182         dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
  1183       dij.run(Base::_source);
  1184     }
  1185 
  1186     ///Runs Dijkstra algorithm from the given node.
  1187 
  1188     ///Runs Dijkstra algorithm from the given node.
  1189     ///\param s is the given source.
  1190     void run(Node s)
  1191     {
  1192       Base::_source=s;
  1193       run();
  1194     }
  1195 
  1196     /// Sets the source node, from which the Dijkstra algorithm runs.
  1197 
  1198     /// Sets the source node, from which the Dijkstra algorithm runs.
  1199     /// \param s is the source node.
  1200     DijkstraWizard<TR> &source(Node s)
  1201     {
  1202       Base::_source=s;
  1203       return *this;
  1204     }
  1205 
  1206     template<class T>
  1207     struct SetPredMapBase : public Base {
  1208       typedef T PredMap;
  1209       static PredMap *createPredMap(const Digraph &) { return 0; };
  1210       SetPredMapBase(const TR &b) : TR(b) {}
  1211     };
  1212     ///\brief \ref named-templ-param "Named parameter"
  1213     ///for setting \ref PredMap object.
  1214     ///
  1215     ///\ref named-templ-param "Named parameter"
  1216     ///for setting \ref PredMap object.
  1217     template<class T>
  1218     DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
  1219     {
  1220       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1221       return DijkstraWizard<SetPredMapBase<T> >(*this);
  1222     }
  1223 
  1224     template<class T>
  1225     struct SetProcessedMapBase : public Base {
  1226       typedef T ProcessedMap;
  1227       static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  1228       SetProcessedMapBase(const TR &b) : TR(b) {}
  1229     };
  1230     ///\brief \ref named-templ-param "Named parameter"
  1231     ///for setting \ref ProcessedMap object.
  1232     ///
  1233     /// \ref named-templ-param "Named parameter"
  1234     ///for setting \ref ProcessedMap object.
  1235     template<class T>
  1236     DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
  1237     {
  1238       Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
  1239       return DijkstraWizard<SetProcessedMapBase<T> >(*this);
  1240     }
  1241 
  1242     template<class T>
  1243     struct SetDistMapBase : public Base {
  1244       typedef T DistMap;
  1245       static DistMap *createDistMap(const Digraph &) { return 0; };
  1246       SetDistMapBase(const TR &b) : TR(b) {}
  1247     };
  1248     ///\brief \ref named-templ-param "Named parameter"
  1249     ///for setting \ref DistMap object.
  1250     ///
  1251     ///\ref named-templ-param "Named parameter"
  1252     ///for setting \ref DistMap object.
  1253     template<class T>
  1254     DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
  1255     {
  1256       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
  1257       return DijkstraWizard<SetDistMapBase<T> >(*this);
  1258     }
  1259 
  1260   };
  1261 
  1262   ///Function type interface for Dijkstra algorithm.
  1263 
  1264   /// \ingroup shortest_path
  1265   ///Function type interface for Dijkstra algorithm.
  1266   ///
  1267   ///This function also has several
  1268   ///\ref named-templ-func-param "named parameters",
  1269   ///they are declared as the members of class \ref DijkstraWizard.
  1270   ///The following
  1271   ///example shows how to use these parameters.
  1272   ///\code
  1273   ///  dijkstra(g,length,source).predMap(preds).run();
  1274   ///\endcode
  1275   ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
  1276   ///to the end of the parameter list.
  1277   ///\sa DijkstraWizard
  1278   ///\sa Dijkstra
  1279   template<class GR, class LM>
  1280   DijkstraWizard<DijkstraWizardBase<GR,LM> >
  1281   dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
  1282   {
  1283     return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
  1284   }
  1285 
  1286 } //END OF NAMESPACE LEMON
  1287 
  1288 #endif