COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dijkstra.h @ 257:8d76a7bf9961

Last change on this file since 257:8d76a7bf9961 was 257:8d76a7bf9961, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Rename Def* to Set* in Bfs, Dfs, Dijkstra (ticket #134)

File size: 42.0 KB
RevLine 
[209]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[100]2 *
[209]3 * This file is a part of LEMON, a generic C++ optimization library.
[100]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
[184]26#include <limits>
[169]27#include <lemon/list_graph.h>
[100]28#include <lemon/bin_heap.h>
29#include <lemon/bits/path_dump.h>
[220]30#include <lemon/core.h>
[100]31#include <lemon/error.h>
32#include <lemon/maps.h>
33
34namespace lemon {
35
[244]36  /// \brief Default operation traits for the Dijkstra algorithm class.
[209]37  ///
[244]38  /// This operation traits class defines all computational operations and
39  /// constants which are used in the Dijkstra algorithm.
[100]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    }
[244]50    /// \brief Gives back true only if the first value is less than the second.
[100]51    static bool less(const Value& left, const Value& right) {
52      return left < right;
53    }
54  };
55
[244]56  /// \brief Widest path operation traits for the Dijkstra algorithm class.
[209]57  ///
[244]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
[100]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    }
[244]73    /// \brief Gives back true only if the first value is less than the second.
[100]74    static bool less(const Value& left, const Value& right) {
75      return left < right;
76    }
77  };
[209]78
[100]79  ///Default traits class of Dijkstra class.
80
81  ///Default traits class of Dijkstra class.
[244]82  ///\tparam GR The type of the digraph.
83  ///\tparam LM The type of the length map.
[100]84  template<class GR, class LM>
85  struct DijkstraDefaultTraits
86  {
[244]87    ///The type of the digraph the algorithm runs on.
[100]88    typedef GR Digraph;
[244]89
[100]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;
[244]95    ///The type of the length of the arcs.
[100]96    typedef typename LM::Value Value;
[244]97
[100]98    /// Operation traits for Dijkstra algorithm.
99
[244]100    /// This class defines the operations that are used in the algorithm.
[100]101    /// \see DijkstraDefaultOperationTraits
102    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
103
[244]104    /// The cross reference type used by the heap.
[100]105
[244]106    /// The cross reference type used by the heap.
[100]107    /// Usually it is \c Digraph::NodeMap<int>.
108    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
[244]109    ///Instantiates a \ref HeapCrossRef.
[100]110
[244]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)
[100]115    {
[244]116      return new HeapCrossRef(g);
[100]117    }
[209]118
[244]119    ///The heap type used by the Dijkstra algorithm.
[100]120
[244]121    ///The heap type used by the Dijkstra algorithm.
[100]122    ///
123    ///\sa BinHeap
124    ///\sa Dijkstra
125    typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
[244]126    ///Instantiates a \ref Heap.
[100]127
[244]128    ///This function instantiates a \ref Heap.
129    static Heap *createHeap(HeapCrossRef& r)
[100]130    {
[244]131      return new Heap(r);
[100]132    }
133
[244]134    ///\brief The type of the map that stores the predecessor
[100]135    ///arcs of the shortest paths.
[209]136    ///
[244]137    ///The type of the map that stores the predecessor
[100]138    ///arcs of the shortest paths.
139    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
[244]140    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
141    ///Instantiates a \ref PredMap.
[209]142
[244]143    ///This function instantiates a \ref PredMap.
144    ///\param g is the digraph, to which we would like to define the
145    ///\ref PredMap.
[100]146    ///\todo The digraph alone may be insufficient for the initialization
[244]147    static PredMap *createPredMap(const Digraph &g)
[100]148    {
[244]149      return new PredMap(g);
[100]150    }
151
[244]152    ///The type of the map that indicates which nodes are processed.
[209]153
[244]154    ///The type of the map that indicates which nodes are processed.
[100]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;
[244]160    ///Instantiates a \ref ProcessedMap.
[209]161
[244]162    ///This function instantiates a \ref ProcessedMap.
[100]163    ///\param g is the digraph, to which
[244]164    ///we would like to define the \ref ProcessedMap
[100]165#ifdef DOXYGEN
[244]166    static ProcessedMap *createProcessedMap(const Digraph &g)
[100]167#else
[244]168    static ProcessedMap *createProcessedMap(const Digraph &)
[100]169#endif
170    {
171      return new ProcessedMap();
172    }
[209]173
[244]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.
[100]177    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
178    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
[244]179    ///Instantiates a \ref DistMap.
[209]180
181    ///This function instantiates a \ref DistMap.
[244]182    ///\param g is the digraph, to which we would like to define
[210]183    ///the \ref DistMap
[244]184    static DistMap *createDistMap(const Digraph &g)
[100]185    {
[244]186      return new DistMap(g);
[100]187    }
188  };
[209]189
[100]190  ///%Dijkstra algorithm class.
[209]191
[100]192  /// \ingroup shortest_path
[244]193  ///This class provides an efficient implementation of the %Dijkstra algorithm.
194  ///
[100]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  ///
[244]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
[100]211  ///arcs. It is read once for each arc, so the map may involve in
[244]212  ///relatively time consuming process to compute the arc lengths if
[100]213  ///it is necessary. The default map type is \ref
[244]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.
[100]221#ifdef DOXYGEN
222  template <typename GR, typename LM, typename TR>
223#else
224  template <typename GR=ListDigraph,
[209]225            typename LM=typename GR::template ArcMap<int>,
226            typename TR=DijkstraDefaultTraits<GR,LM> >
[100]227#endif
228  class Dijkstra {
229  public:
[244]230    ///\ref Exception for uninitialized parameters.
231
232    ///This error represents problems in the initialization of the
233    ///parameters of the algorithm.
[100]234    class UninitializedParameter : public lemon::UninitializedParameter {
235    public:
236      virtual const char* what() const throw() {
[209]237        return "lemon::Dijkstra::UninitializedParameter";
[100]238      }
239    };
240
[244]241    ///The type of the digraph the algorithm runs on.
[100]242    typedef typename TR::Digraph Digraph;
[209]243
[100]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;
[244]248    ///\brief The type of the map that stores the predecessor arcs of the
249    ///shortest paths.
[100]250    typedef typename TR::PredMap PredMap;
[244]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.
[100]254    typedef typename TR::ProcessedMap ProcessedMap;
[244]255    ///The type of the paths.
256    typedef PredMapPath<Digraph, PredMap> Path;
[100]257    ///The cross reference type used for the current heap.
258    typedef typename TR::HeapCrossRef HeapCrossRef;
[244]259    ///The heap type used by the algorithm.
[100]260    typedef typename TR::Heap Heap;
[244]261    ///The operation traits class.
[100]262    typedef typename TR::OperationTraits OperationTraits;
[244]263
264    ///The traits class.
265    typedef TR Traits;
266
[100]267  private:
[244]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.
[100]275    const Digraph *G;
[244]276    //Pointer to the length map.
[100]277    const LengthMap *length;
[244]278    //Pointer to the map of predecessors arcs.
[100]279    PredMap *_pred;
[244]280    //Indicates if _pred is locally allocated (true) or not.
[100]281    bool local_pred;
[244]282    //Pointer to the map of distances.
[100]283    DistMap *_dist;
[244]284    //Indicates if _dist is locally allocated (true) or not.
[100]285    bool local_dist;
[244]286    //Pointer to the map of processed status of the nodes.
[100]287    ProcessedMap *_processed;
[244]288    //Indicates if _processed is locally allocated (true) or not.
[100]289    bool local_processed;
[244]290    //Pointer to the heap cross references.
[100]291    HeapCrossRef *_heap_cross_ref;
[244]292    //Indicates if _heap_cross_ref is locally allocated (true) or not.
[100]293    bool local_heap_cross_ref;
[244]294    //Pointer to the heap.
[100]295    Heap *_heap;
[244]296    //Indicates if _heap is locally allocated (true) or not.
[100]297    bool local_heap;
298
299    ///Creates the maps if necessary.
300    ///\todo Better memory allocation (instead of new).
[209]301    void create_maps()
[100]302    {
303      if(!_pred) {
[209]304        local_pred = true;
305        _pred = Traits::createPredMap(*G);
[100]306      }
307      if(!_dist) {
[209]308        local_dist = true;
309        _dist = Traits::createDistMap(*G);
[100]310      }
311      if(!_processed) {
[209]312        local_processed = true;
313        _processed = Traits::createProcessedMap(*G);
[100]314      }
315      if (!_heap_cross_ref) {
[209]316        local_heap_cross_ref = true;
317        _heap_cross_ref = Traits::createHeapCrossRef(*G);
[100]318      }
319      if (!_heap) {
[209]320        local_heap = true;
321        _heap = Traits::createHeap(*_heap_cross_ref);
[100]322      }
323    }
[209]324
[244]325  public:
[100]326
327    typedef Dijkstra Create;
[209]328
[100]329    ///\name Named template parameters
330
331    ///@{
332
333    template <class T>
[257]334    struct SetPredMapTraits : public Traits {
[100]335      typedef T PredMap;
336      static PredMap *createPredMap(const Digraph &)
337      {
[209]338        throw UninitializedParameter();
[100]339      }
340    };
[244]341    ///\brief \ref named-templ-param "Named parameter" for setting
342    ///\ref PredMap type.
[100]343    ///
[244]344    ///\ref named-templ-param "Named parameter" for setting
345    ///\ref PredMap type.
[100]346    template <class T>
[257]347    struct SetPredMap
348      : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
349      typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
[100]350    };
[209]351
[100]352    template <class T>
[257]353    struct SetDistMapTraits : public Traits {
[100]354      typedef T DistMap;
355      static DistMap *createDistMap(const Digraph &)
356      {
[209]357        throw UninitializedParameter();
[100]358      }
359    };
[244]360    ///\brief \ref named-templ-param "Named parameter" for setting
361    ///\ref DistMap type.
[100]362    ///
[244]363    ///\ref named-templ-param "Named parameter" for setting
364    ///\ref DistMap type.
[100]365    template <class T>
[257]366    struct SetDistMap
367      : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
368      typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
[100]369    };
[209]370
[100]371    template <class T>
[257]372    struct SetProcessedMapTraits : public Traits {
[100]373      typedef T ProcessedMap;
[244]374      static ProcessedMap *createProcessedMap(const Digraph &)
[100]375      {
[209]376        throw UninitializedParameter();
[100]377      }
378    };
[244]379    ///\brief \ref named-templ-param "Named parameter" for setting
380    ///\ref ProcessedMap type.
[100]381    ///
[244]382    ///\ref named-templ-param "Named parameter" for setting
383    ///\ref ProcessedMap type.
[100]384    template <class T>
[257]385    struct SetProcessedMap
386      : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
387      typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
[100]388    };
[209]389
[257]390    struct SetStandardProcessedMapTraits : public Traits {
[100]391      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
[244]392      static ProcessedMap *createProcessedMap(const Digraph &g)
[100]393      {
[244]394        return new ProcessedMap(g);
[100]395      }
396    };
[244]397    ///\brief \ref named-templ-param "Named parameter" for setting
398    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
[100]399    ///
[244]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.
[257]403    struct SetStandardProcessedMap
404      : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
405      typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >
[210]406      Create;
[100]407    };
408
409    template <class H, class CR>
[257]410    struct SetHeapTraits : public Traits {
[100]411      typedef CR HeapCrossRef;
412      typedef H Heap;
413      static HeapCrossRef *createHeapCrossRef(const Digraph &) {
[209]414        throw UninitializedParameter();
[100]415      }
[209]416      static Heap *createHeap(HeapCrossRef &)
[100]417      {
[209]418        throw UninitializedParameter();
[100]419      }
420    };
421    ///\brief \ref named-templ-param "Named parameter" for setting
422    ///heap and cross reference type
423    ///
[209]424    ///\ref named-templ-param "Named parameter" for setting heap and cross
[244]425    ///reference type.
[100]426    template <class H, class CR = typename Digraph::template NodeMap<int> >
[257]427    struct SetHeap
428      : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
429      typedef Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > Create;
[100]430    };
431
432    template <class H, class CR>
[257]433    struct SetStandardHeapTraits : public Traits {
[100]434      typedef CR HeapCrossRef;
435      typedef H Heap;
436      static HeapCrossRef *createHeapCrossRef(const Digraph &G) {
[209]437        return new HeapCrossRef(G);
[100]438      }
[209]439      static Heap *createHeap(HeapCrossRef &R)
[100]440      {
[209]441        return new Heap(R);
[100]442      }
443    };
444    ///\brief \ref named-templ-param "Named parameter" for setting
445    ///heap and cross reference type with automatic allocation
446    ///
[209]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
[100]450    ///parameter and the heap's constructor waits for the cross reference.
451    template <class H, class CR = typename Digraph::template NodeMap<int> >
[257]452    struct SetStandardHeap
453      : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
454      typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> >
[100]455      Create;
456    };
457
458    template <class T>
[257]459    struct SetOperationTraitsTraits : public Traits {
[100]460      typedef T OperationTraits;
461    };
[209]462
463    /// \brief \ref named-templ-param "Named parameter" for setting
[244]464    ///\ref OperationTraits type
[100]465    ///
[244]466    ///\ref named-templ-param "Named parameter" for setting
467    ///\ref OperationTraits type.
[100]468    template <class T>
[257]469    struct SetOperationTraits
470      : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
471      typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >
[100]472      Create;
473    };
[209]474
[100]475    ///@}
476
477  protected:
478
479    Dijkstra() {}
480
[209]481  public:
482
[100]483    ///Constructor.
[209]484
[244]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),
[100]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    { }
[209]496
[100]497    ///Destructor.
[209]498    ~Dijkstra()
[100]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>
[209]511    Dijkstra &lengthMap(const LengthMap &m)
[100]512    {
513      length = &m;
514      return *this;
515    }
516
[244]517    ///Sets the map that stores the predecessor arcs.
[100]518
[244]519    ///Sets the map that stores the predecessor arcs.
[100]520    ///If you don't use this function before calling \ref run(),
[244]521    ///it will allocate one. The destructor deallocates this
[100]522    ///automatically allocated map, of course.
523    ///\return <tt> (*this) </tt>
[209]524    Dijkstra &predMap(PredMap &m)
[100]525    {
526      if(local_pred) {
[209]527        delete _pred;
528        local_pred=false;
[100]529      }
530      _pred = &m;
531      return *this;
532    }
533
[244]534    ///Sets the map that indicates which nodes are processed.
[100]535
[244]536    ///Sets the map that indicates which nodes are processed.
[100]537    ///If you don't use this function before calling \ref run(),
[244]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
[100]557    ///automatically allocated map, of course.
558    ///\return <tt> (*this) </tt>
[209]559    Dijkstra &distMap(DistMap &m)
[100]560    {
561      if(local_dist) {
[209]562        delete _dist;
563        local_dist=false;
[100]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(),
[244]573    ///it will allocate one. The destructor deallocates this
[100]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) {
[209]579        delete _heap_cross_ref;
580        local_heap_cross_ref=false;
[100]581      }
582      _heap_cross_ref = &cr;
583      if(local_heap) {
[209]584        delete _heap;
585        local_heap=false;
[100]586      }
587      _heap = &hp;
588      return *this;
589    }
590
591  private:
[244]592
[100]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
[244]602    ///The simplest way to execute the algorithm is to use one of the
603    ///member functions called \ref lemon::Dijkstra::run() "run()".
[100]604    ///\n
[244]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.
[100]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 ) {
[209]622        _pred->set(u,INVALID);
623        _processed->set(u,false);
624        _heap_cross_ref->set(u,Heap::PRE_HEAP);
[100]625      }
626    }
[209]627
[100]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    ///
[244]633    ///The function checks if the node has already been added to the heap and
[100]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) {
[209]639        _heap->push(s,dst);
[100]640      } else if(OperationTraits::less((*_heap)[s], dst)) {
[209]641        _heap->set(s,dst);
642        _pred->set(s,INVALID);
[100]643      }
644    }
[209]645
[100]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    ///
[244]652    ///\warning The priority heap must not be empty.
[100]653    Node processNextNode()
654    {
[209]655      Node v=_heap->top();
[100]656      Value oldvalue=_heap->prio();
657      _heap->pop();
658      finalizeNodeData(v,oldvalue);
[209]659
[100]660      for(OutArcIt e(*G,v); e!=INVALID; ++e) {
[209]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        }
[100]679      }
680      return v;
681    }
682
[244]683    ///The next node to be processed.
[209]684
[244]685    ///Returns the next node to be processed or \c INVALID if the
686    ///priority heap is empty.
687    Node nextNode() const
[209]688    {
[100]689      return !_heap->empty()?_heap->top():INVALID;
690    }
[209]691
[100]692    ///\brief Returns \c false if there are nodes
[244]693    ///to be processed.
[100]694    ///
695    ///Returns \c false if there are nodes
[244]696    ///to be processed in the priority heap.
697    bool emptyQueue() const { return _heap->empty(); }
698
[100]699    ///Returns the number of the nodes to be processed in the priority heap
700
[244]701    ///Returns the number of the nodes to be processed in the priority heap.
[100]702    ///
[244]703    int queueSize() const { return _heap->size(); }
[209]704
[100]705    ///Executes the algorithm.
706
707    ///Executes the algorithm.
708    ///
[244]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.
[100]733    ///
734    ///This method runs the %Dijkstra algorithm from the root node(s)
[244]735    ///in order to compute the shortest path to \c dest.
[100]736    ///
[244]737    ///The algorithm computes
738    ///- the shortest path to \c dest,
739    ///- the distance of \c dest from the root(s).
[100]740    ///
[244]741    ///\pre init() must be called and at least one root node should be
742    ///added with addSource() before using this function.
[100]743    void start(Node dest)
744    {
745      while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
746      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
747    }
[209]748
[100]749    ///Executes the algorithm until a condition is met.
750
751    ///Executes the algorithm until a condition is met.
752    ///
[244]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.
[100]756    ///
[244]757    ///\param nm A \c bool (or convertible) node map. The algorithm
[100]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.
[244]762    ///
763    ///\pre init() must be called and at least one root node should be
764    ///added with addSource() before using this function.
[100]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    }
[209]773
[244]774    ///Runs the algorithm from the given node.
[209]775
[244]776    ///This method runs the %Dijkstra algorithm from node \c s
777    ///in order to compute the shortest path to each node.
[100]778    ///
[244]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.
[100]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    }
[209]794
[100]795    ///Finds the shortest path between \c s and \c t.
[209]796
[244]797    ///This method runs the %Dijkstra algorithm from node \c s
798    ///in order to compute the shortest path to \c t.
[100]799    ///
[244]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.
[100]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    }
[209]816
[100]817    ///@}
818
819    ///\name Query Functions
820    ///The result of the %Dijkstra algorithm can be obtained using these
821    ///functions.\n
[244]822    ///Either \ref lemon::Dijkstra::run() "run()" or
823    ///\ref lemon::Dijkstra::start() "start()" must be called before
824    ///using them.
[209]825
[100]826    ///@{
827
[244]828    ///The shortest path to a node.
[209]829
[244]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); }
[100]837
[244]838    ///The distance of a node from the root(s).
[100]839
[244]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.
[100]847    Value dist(Node v) const { return (*_dist)[v]; }
848
[244]849    ///Returns the 'previous arc' of the shortest path tree for a node.
[100]850
[244]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.
[100]861    Arc predArc(Node v) const { return (*_pred)[v]; }
862
[244]863    ///Returns the 'previous node' of the shortest path tree for a node.
[100]864
[244]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
[100]874    ///using this function.
875    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
[209]876                                  G->source((*_pred)[v]); }
877
[244]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.
[100]886    const DistMap &distMap() const { return *_dist;}
[209]887
[244]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.
[100]896    const PredMap &predMap() const { return *_pred;}
[209]897
[244]898    ///Checks if a node is reachable from the root(s).
[100]899
[244]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; }
[100]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.
[244]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]; }
[209]921
[100]922    ///@}
923  };
924
925
[244]926  ///Default traits class of dijkstra() function.
[100]927
[244]928  ///Default traits class of dijkstra() function.
929  ///\tparam GR The type of the digraph.
930  ///\tparam LM The type of the length map.
[100]931  template<class GR, class LM>
932  struct DijkstraWizardDefaultTraits
933  {
[244]934    ///The type of the digraph the algorithm runs on.
[100]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;
[244]941    ///The type of the length of the arcs.
[100]942    typedef typename LM::Value Value;
[244]943
[100]944    /// Operation traits for Dijkstra algorithm.
945
[244]946    /// This class defines the operations that are used in the algorithm.
[100]947    /// \see DijkstraDefaultOperationTraits
948    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
949
[244]950    /// The cross reference type used by the heap.
[100]951
[244]952    /// The cross reference type used by the heap.
[100]953    /// Usually it is \c Digraph::NodeMap<int>.
954    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
[244]955    ///Instantiates a \ref HeapCrossRef.
[100]956
[209]957    ///This function instantiates a \ref HeapCrossRef.
[244]958    /// \param g is the digraph, to which we would like to define the
[100]959    /// HeapCrossRef.
960    /// \todo The digraph alone may be insufficient for the initialization
[244]961    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
[100]962    {
[244]963      return new HeapCrossRef(g);
[100]964    }
[209]965
[244]966    ///The heap type used by the Dijkstra algorithm.
[100]967
[244]968    ///The heap type used by the Dijkstra algorithm.
[100]969    ///
970    ///\sa BinHeap
971    ///\sa Dijkstra
[244]972    typedef BinHeap<Value, typename Digraph::template NodeMap<int>,
[209]973                    std::less<Value> > Heap;
[100]974
[244]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)
[100]980    {
[244]981      return new Heap(r);
[100]982    }
983
[244]984    ///\brief The type of the map that stores the predecessor
[100]985    ///arcs of the shortest paths.
[209]986    ///
[244]987    ///The type of the map that stores the predecessor
[100]988    ///arcs of the shortest paths.
989    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
[244]990    typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;
991    ///Instantiates a \ref PredMap.
[209]992
993    ///This function instantiates a \ref PredMap.
[244]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
[100]997#ifdef DOXYGEN
[244]998    static PredMap *createPredMap(const Digraph &g)
[100]999#else
[244]1000    static PredMap *createPredMap(const Digraph &)
[100]1001#endif
1002    {
1003      return new PredMap();
1004    }
[209]1005
[244]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.
[100]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;
[244]1015    ///Instantiates a \ref ProcessedMap.
[209]1016
1017    ///This function instantiates a \ref ProcessedMap.
[100]1018    ///\param g is the digraph, to which
[244]1019    ///we would like to define the \ref ProcessedMap.
[100]1020#ifdef DOXYGEN
[244]1021    static ProcessedMap *createProcessedMap(const Digraph &g)
[100]1022#else
[244]1023    static ProcessedMap *createProcessedMap(const Digraph &)
[100]1024#endif
1025    {
1026      return new ProcessedMap();
1027    }
[209]1028
[244]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.
[100]1032    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
[244]1033    typedef NullMap<typename Digraph::Node,Value> DistMap;
1034    ///Instantiates a \ref DistMap.
[209]1035
1036    ///This function instantiates a \ref DistMap.
[210]1037    ///\param g is the digraph, to which we would like to define
1038    ///the \ref DistMap
[100]1039#ifdef DOXYGEN
[244]1040    static DistMap *createDistMap(const Digraph &g)
[100]1041#else
[244]1042    static DistMap *createDistMap(const Digraph &)
[100]1043#endif
1044    {
1045      return new DistMap();
1046    }
1047  };
[209]1048
[244]1049  /// Default traits class used by \ref DijkstraWizard
[100]1050
1051  /// To make it easier to use Dijkstra algorithm
[244]1052  /// we have created a wizard class.
[100]1053  /// This \ref DijkstraWizard class needs default traits,
[244]1054  /// as well as the \ref Dijkstra class.
[100]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:
[244]1063    //The type of the nodes in the digraph.
[100]1064    typedef typename Base::Digraph::Node Node;
1065
[244]1066    //Pointer to the digraph the algorithm runs on.
[100]1067    void *_g;
[244]1068    //Pointer to the length map
[100]1069    void *_length;
[244]1070    //Pointer to the map of predecessors arcs.
[100]1071    void *_pred;
[244]1072    //Pointer to the map of distances.
[100]1073    void *_dist;
[244]1074    //Pointer to the source node.
[100]1075    Node _source;
1076
[244]1077  public:
[100]1078    /// Constructor.
[209]1079
[100]1080    /// This constructor does not require parameters, therefore it initiates
1081    /// all of the attributes to default values (0, INVALID).
1082    DijkstraWizardBase() : _g(0), _length(0), _pred(0),
[209]1083                           _dist(0), _source(INVALID) {}
[100]1084
1085    /// Constructor.
[209]1086
[100]1087    /// This constructor requires some parameters,
1088    /// listed in the parameters list.
1089    /// Others are initiated to 0.
[244]1090    /// \param g The digraph the algorithm runs on.
1091    /// \param l The length map.
1092    /// \param s The source node.
[100]1093    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
[209]1094      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1095      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
[100]1096      _pred(0), _dist(0), _source(s) {}
1097
1098  };
[209]1099
[244]1100  /// Auxiliary class for the function type interface of Dijkstra algorithm.
[100]1101
[244]1102  /// This auxiliary class is created to implement the function type
1103  /// interface of \ref Dijkstra algorithm. It uses the functions and features
1104  /// of the plain \ref Dijkstra, but it is much simpler to use it.
1105  /// It should only be used through the \ref dijkstra() function, which makes
1106  /// it easier to use the algorithm.
[100]1107  ///
1108  /// Simplicity means that the way to change the types defined
1109  /// in the traits class is based on functions that returns the new class
1110  /// and not on templatable built-in classes.
1111  /// When using the plain \ref Dijkstra
1112  /// the new class with the modified type comes from
1113  /// the original class by using the ::
1114  /// operator. In the case of \ref DijkstraWizard only
[244]1115  /// a function have to be called, and it will
[100]1116  /// return the needed class.
1117  ///
[244]1118  /// It does not have own \ref run() method. When its \ref run() method
1119  /// is called, it initiates a plain \ref Dijkstra object, and calls the
1120  /// \ref Dijkstra::run() method of it.
[100]1121  template<class TR>
1122  class DijkstraWizard : public TR
1123  {
1124    typedef TR Base;
1125
[244]1126    ///The type of the digraph the algorithm runs on.
[100]1127    typedef typename TR::Digraph Digraph;
[244]1128
[100]1129    typedef typename Digraph::Node Node;
1130    typedef typename Digraph::NodeIt NodeIt;
1131    typedef typename Digraph::Arc Arc;
1132    typedef typename Digraph::OutArcIt OutArcIt;
[209]1133
[100]1134    ///The type of the map that stores the arc lengths.
1135    typedef typename TR::LengthMap LengthMap;
1136    ///The type of the length of the arcs.
1137    typedef typename LengthMap::Value Value;
[244]1138    ///\brief The type of the map that stores the predecessor
[100]1139    ///arcs of the shortest paths.
1140    typedef typename TR::PredMap PredMap;
[244]1141    ///The type of the map that stores the distances of the nodes.
[100]1142    typedef typename TR::DistMap DistMap;
[244]1143    ///The type of the map that indicates which nodes are processed.
1144    typedef typename TR::ProcessedMap ProcessedMap;
[100]1145    ///The heap type used by the dijkstra algorithm.
1146    typedef typename TR::Heap Heap;
[244]1147
[100]1148  public:
[244]1149
[100]1150    /// Constructor.
1151    DijkstraWizard() : TR() {}
1152
1153    /// Constructor that requires parameters.
1154
1155    /// Constructor that requires parameters.
1156    /// These parameters will be the default values for the traits class.
1157    DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) :
1158      TR(g,l,s) {}
1159
1160    ///Copy constructor
1161    DijkstraWizard(const TR &b) : TR(b) {}
1162
1163    ~DijkstraWizard() {}
1164
[244]1165    ///Runs Dijkstra algorithm from a source node.
[209]1166
[244]1167    ///Runs Dijkstra algorithm from a source node.
1168    ///The node can be given with the \ref source() function.
[100]1169    void run()
1170    {
1171      if(Base::_source==INVALID) throw UninitializedParameter();
[209]1172      Dijkstra<Digraph,LengthMap,TR>
1173        dij(*reinterpret_cast<const Digraph*>(Base::_g),
[100]1174            *reinterpret_cast<const LengthMap*>(Base::_length));
1175      if(Base::_pred) dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1176      if(Base::_dist) dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1177      dij.run(Base::_source);
1178    }
1179
1180    ///Runs Dijkstra algorithm from the given node.
1181
1182    ///Runs Dijkstra algorithm from the given node.
1183    ///\param s is the given source.
1184    void run(Node s)
1185    {
1186      Base::_source=s;
1187      run();
1188    }
1189
[244]1190    /// Sets the source node, from which the Dijkstra algorithm runs.
1191
1192    /// Sets the source node, from which the Dijkstra algorithm runs.
1193    /// \param s is the source node.
1194    DijkstraWizard<TR> &source(Node s)
1195    {
1196      Base::_source=s;
1197      return *this;
1198    }
1199
[100]1200    template<class T>
[257]1201    struct SetPredMapBase : public Base {
[100]1202      typedef T PredMap;
1203      static PredMap *createPredMap(const Digraph &) { return 0; };
[257]1204      SetPredMapBase(const TR &b) : TR(b) {}
[100]1205    };
1206    ///\brief \ref named-templ-param "Named parameter"
[244]1207    ///for setting \ref PredMap object.
[100]1208    ///
[244]1209    ///\ref named-templ-param "Named parameter"
1210    ///for setting \ref PredMap object.
[100]1211    template<class T>
[257]1212    DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
[100]1213    {
1214      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
[257]1215      return DijkstraWizard<SetPredMapBase<T> >(*this);
[100]1216    }
[209]1217
[100]1218    template<class T>
[257]1219    struct SetProcessedMapBase : public Base {
[244]1220      typedef T ProcessedMap;
1221      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
[257]1222      SetProcessedMapBase(const TR &b) : TR(b) {}
[244]1223    };
1224    ///\brief \ref named-templ-param "Named parameter"
1225    ///for setting \ref ProcessedMap object.
1226    ///
1227    /// \ref named-templ-param "Named parameter"
1228    ///for setting \ref ProcessedMap object.
1229    template<class T>
[257]1230    DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
[244]1231    {
1232      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
[257]1233      return DijkstraWizard<SetProcessedMapBase<T> >(*this);
[244]1234    }
1235
1236    template<class T>
[257]1237    struct SetDistMapBase : public Base {
[100]1238      typedef T DistMap;
1239      static DistMap *createDistMap(const Digraph &) { return 0; };
[257]1240      SetDistMapBase(const TR &b) : TR(b) {}
[100]1241    };
1242    ///\brief \ref named-templ-param "Named parameter"
[244]1243    ///for setting \ref DistMap object.
[100]1244    ///
[244]1245    ///\ref named-templ-param "Named parameter"
1246    ///for setting \ref DistMap object.
[100]1247    template<class T>
[257]1248    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
[100]1249    {
1250      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
[257]1251      return DijkstraWizard<SetDistMapBase<T> >(*this);
[100]1252    }
[209]1253
[100]1254  };
[209]1255
[100]1256  ///Function type interface for Dijkstra algorithm.
1257
1258  /// \ingroup shortest_path
1259  ///Function type interface for Dijkstra algorithm.
1260  ///
1261  ///This function also has several
1262  ///\ref named-templ-func-param "named parameters",
1263  ///they are declared as the members of class \ref DijkstraWizard.
1264  ///The following
1265  ///example shows how to use these parameters.
1266  ///\code
1267  ///  dijkstra(g,length,source).predMap(preds).run();
1268  ///\endcode
1269  ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
1270  ///to the end of the parameter list.
1271  ///\sa DijkstraWizard
1272  ///\sa Dijkstra
1273  template<class GR, class LM>
1274  DijkstraWizard<DijkstraWizardBase<GR,LM> >
1275  dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
1276  {
1277    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
1278  }
1279
1280} //END OF NAMESPACE LEMON
1281
1282#endif
Note: See TracBrowser for help on using the repository browser.