1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_DIJKSTRA_H
20 #define LEMON_DIJKSTRA_H
22 ///\ingroup shortest_path
24 ///\brief Dijkstra algorithm.
27 #include <lemon/list_graph.h>
28 #include <lemon/bin_heap.h>
29 #include <lemon/bits/path_dump.h>
30 #include <lemon/core.h>
31 #include <lemon/error.h>
32 #include <lemon/maps.h>
33 #include <lemon/path.h>
37 /// \brief Default operation traits for the Dijkstra algorithm class.
39 /// This operation traits class defines all computational operations and
40 /// constants which are used in the Dijkstra algorithm.
41 template <typename Value>
42 struct DijkstraDefaultOperationTraits {
43 /// \brief Gives back the zero value of the type.
45 return static_cast<Value>(0);
47 /// \brief Gives back the sum of the given two elements.
48 static Value plus(const Value& left, const Value& right) {
51 /// \brief Gives back true only if the first value is less than the second.
52 static bool less(const Value& left, const Value& right) {
57 /// \brief Widest path operation traits for the Dijkstra algorithm class.
59 /// This operation traits class defines all computational operations and
60 /// constants which are used in the Dijkstra algorithm for widest path
63 /// \see DijkstraDefaultOperationTraits
64 template <typename Value>
65 struct DijkstraWidestPathOperationTraits {
66 /// \brief Gives back the maximum value of the type.
68 return std::numeric_limits<Value>::max();
70 /// \brief Gives back the minimum of the given two elements.
71 static Value plus(const Value& left, const Value& right) {
72 return std::min(left, right);
74 /// \brief Gives back true only if the first value is less than the second.
75 static bool less(const Value& left, const Value& right) {
80 ///Default traits class of Dijkstra class.
82 ///Default traits class of Dijkstra class.
83 ///\tparam GR The type of the digraph.
84 ///\tparam LM The type of the length map.
85 template<class GR, class LM>
86 struct DijkstraDefaultTraits
88 ///The type of the digraph the algorithm runs on.
91 ///The type of the map that stores the arc lengths.
93 ///The type of the map that stores the arc lengths.
94 ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
96 ///The type of the length of the arcs.
97 typedef typename LM::Value Value;
99 /// Operation traits for Dijkstra algorithm.
101 /// This class defines the operations that are used in the algorithm.
102 /// \see DijkstraDefaultOperationTraits
103 typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
105 /// The cross reference type used by the heap.
107 /// The cross reference type used by the heap.
108 /// Usually it is \c Digraph::NodeMap<int>.
109 typedef typename Digraph::template NodeMap<int> HeapCrossRef;
110 ///Instantiates a \ref HeapCrossRef.
112 ///This function instantiates a \ref HeapCrossRef.
113 /// \param g is the digraph, to which we would like to define the
114 /// \ref HeapCrossRef.
115 static HeapCrossRef *createHeapCrossRef(const Digraph &g)
117 return new HeapCrossRef(g);
120 ///The heap type used by the Dijkstra algorithm.
122 ///The heap type used by the Dijkstra algorithm.
126 typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
127 ///Instantiates a \ref Heap.
129 ///This function instantiates a \ref Heap.
130 static Heap *createHeap(HeapCrossRef& r)
135 ///\brief The type of the map that stores the predecessor
136 ///arcs of the shortest paths.
138 ///The type of the map that stores the predecessor
139 ///arcs of the shortest paths.
140 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
141 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
142 ///Instantiates a PredMap.
144 ///This function instantiates a PredMap.
145 ///\param g is the digraph, to which we would like to define the
147 static PredMap *createPredMap(const Digraph &g)
149 return new PredMap(g);
152 ///The type of the map that indicates which nodes are processed.
154 ///The type of the map that indicates which nodes are processed.
155 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
156 ///By default it is a NullMap.
157 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
158 ///Instantiates a ProcessedMap.
160 ///This function instantiates a ProcessedMap.
161 ///\param g is the digraph, to which
162 ///we would like to define the ProcessedMap
164 static ProcessedMap *createProcessedMap(const Digraph &g)
166 static ProcessedMap *createProcessedMap(const Digraph &)
169 return new ProcessedMap();
172 ///The type of the map that stores the distances of the nodes.
174 ///The type of the map that stores the distances of the nodes.
175 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
176 typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
177 ///Instantiates a DistMap.
179 ///This function instantiates a DistMap.
180 ///\param g is the digraph, to which we would like to define
182 static DistMap *createDistMap(const Digraph &g)
184 return new DistMap(g);
188 ///%Dijkstra algorithm class.
190 /// \ingroup shortest_path
191 ///This class provides an efficient implementation of the %Dijkstra algorithm.
193 ///The arc lengths are passed to the algorithm using a
194 ///\ref concepts::ReadMap "ReadMap",
195 ///so it is easy to change it to any kind of length.
196 ///The type of the length is determined by the
197 ///\ref concepts::ReadMap::Value "Value" of the length map.
198 ///It is also possible to change the underlying priority heap.
200 ///There is also a \ref dijkstra() "function-type interface" for the
201 ///%Dijkstra algorithm, which is convenient in the simplier cases and
202 ///it can be used easier.
204 ///\tparam GR The type of the digraph the algorithm runs on.
205 ///The default type is \ref ListDigraph.
206 ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies
207 ///the lengths of the arcs.
208 ///It is read once for each arc, so the map may involve in
209 ///relatively time consuming process to compute the arc lengths if
210 ///it is necessary. The default map type is \ref
211 ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
213 template <typename GR, typename LM, typename TR>
215 template <typename GR=ListDigraph,
216 typename LM=typename GR::template ArcMap<int>,
217 typename TR=DijkstraDefaultTraits<GR,LM> >
222 ///The type of the digraph the algorithm runs on.
223 typedef typename TR::Digraph Digraph;
225 ///The type of the length of the arcs.
226 typedef typename TR::LengthMap::Value Value;
227 ///The type of the map that stores the arc lengths.
228 typedef typename TR::LengthMap LengthMap;
229 ///\brief The type of the map that stores the predecessor arcs of the
231 typedef typename TR::PredMap PredMap;
232 ///The type of the map that stores the distances of the nodes.
233 typedef typename TR::DistMap DistMap;
234 ///The type of the map that indicates which nodes are processed.
235 typedef typename TR::ProcessedMap ProcessedMap;
236 ///The type of the paths.
237 typedef PredMapPath<Digraph, PredMap> Path;
238 ///The cross reference type used for the current heap.
239 typedef typename TR::HeapCrossRef HeapCrossRef;
240 ///The heap type used by the algorithm.
241 typedef typename TR::Heap Heap;
242 ///The operation traits class.
243 typedef typename TR::OperationTraits OperationTraits;
245 ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
250 typedef typename Digraph::Node Node;
251 typedef typename Digraph::NodeIt NodeIt;
252 typedef typename Digraph::Arc Arc;
253 typedef typename Digraph::OutArcIt OutArcIt;
255 //Pointer to the underlying digraph.
257 //Pointer to the length map.
258 const LengthMap *length;
259 //Pointer to the map of predecessors arcs.
261 //Indicates if _pred is locally allocated (true) or not.
263 //Pointer to the map of distances.
265 //Indicates if _dist is locally allocated (true) or not.
267 //Pointer to the map of processed status of the nodes.
268 ProcessedMap *_processed;
269 //Indicates if _processed is locally allocated (true) or not.
270 bool local_processed;
271 //Pointer to the heap cross references.
272 HeapCrossRef *_heap_cross_ref;
273 //Indicates if _heap_cross_ref is locally allocated (true) or not.
274 bool local_heap_cross_ref;
275 //Pointer to the heap.
277 //Indicates if _heap is locally allocated (true) or not.
280 //Creates the maps if necessary.
285 _pred = Traits::createPredMap(*G);
289 _dist = Traits::createDistMap(*G);
292 local_processed = true;
293 _processed = Traits::createProcessedMap(*G);
295 if (!_heap_cross_ref) {
296 local_heap_cross_ref = true;
297 _heap_cross_ref = Traits::createHeapCrossRef(*G);
301 _heap = Traits::createHeap(*_heap_cross_ref);
307 typedef Dijkstra Create;
309 ///\name Named template parameters
314 struct SetPredMapTraits : public Traits {
316 static PredMap *createPredMap(const Digraph &)
318 LEMON_ASSERT(false, "PredMap is not initialized");
319 return 0; // ignore warnings
322 ///\brief \ref named-templ-param "Named parameter" for setting
325 ///\ref named-templ-param "Named parameter" for setting
327 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
330 : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
331 typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
335 struct SetDistMapTraits : public Traits {
337 static DistMap *createDistMap(const Digraph &)
339 LEMON_ASSERT(false, "DistMap is not initialized");
340 return 0; // ignore warnings
343 ///\brief \ref named-templ-param "Named parameter" for setting
346 ///\ref named-templ-param "Named parameter" for setting
348 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
351 : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
352 typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
356 struct SetProcessedMapTraits : public Traits {
357 typedef T ProcessedMap;
358 static ProcessedMap *createProcessedMap(const Digraph &)
360 LEMON_ASSERT(false, "ProcessedMap is not initialized");
361 return 0; // ignore warnings
364 ///\brief \ref named-templ-param "Named parameter" for setting
365 ///ProcessedMap type.
367 ///\ref named-templ-param "Named parameter" for setting
368 ///ProcessedMap type.
369 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
371 struct SetProcessedMap
372 : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
373 typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
376 struct SetStandardProcessedMapTraits : public Traits {
377 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
378 static ProcessedMap *createProcessedMap(const Digraph &g)
380 return new ProcessedMap(g);
383 ///\brief \ref named-templ-param "Named parameter" for setting
384 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
386 ///\ref named-templ-param "Named parameter" for setting
387 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
388 ///If you don't set it explicitly, it will be automatically allocated.
389 struct SetStandardProcessedMap
390 : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
391 typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >
395 template <class H, class CR>
396 struct SetHeapTraits : public Traits {
397 typedef CR HeapCrossRef;
399 static HeapCrossRef *createHeapCrossRef(const Digraph &) {
400 LEMON_ASSERT(false, "HeapCrossRef is not initialized");
401 return 0; // ignore warnings
403 static Heap *createHeap(HeapCrossRef &)
405 LEMON_ASSERT(false, "Heap is not initialized");
406 return 0; // ignore warnings
409 ///\brief \ref named-templ-param "Named parameter" for setting
410 ///heap and cross reference types
412 ///\ref named-templ-param "Named parameter" for setting heap and cross
413 ///reference types. If this named parameter is used, then external
414 ///heap and cross reference objects must be passed to the algorithm
415 ///using the \ref heap() function before calling \ref run(Node) "run()"
417 ///\sa SetStandardHeap
418 template <class H, class CR = typename Digraph::template NodeMap<int> >
420 : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
421 typedef Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > Create;
424 template <class H, class CR>
425 struct SetStandardHeapTraits : public Traits {
426 typedef CR HeapCrossRef;
428 static HeapCrossRef *createHeapCrossRef(const Digraph &G) {
429 return new HeapCrossRef(G);
431 static Heap *createHeap(HeapCrossRef &R)
436 ///\brief \ref named-templ-param "Named parameter" for setting
437 ///heap and cross reference types with automatic allocation
439 ///\ref named-templ-param "Named parameter" for setting heap and cross
440 ///reference types with automatic allocation.
441 ///They should have standard constructor interfaces to be able to
442 ///automatically created by the algorithm (i.e. the digraph should be
443 ///passed to the constructor of the cross reference and the cross
444 ///reference should be passed to the constructor of the heap).
445 ///However external heap and cross reference objects could also be
446 ///passed to the algorithm using the \ref heap() function before
447 ///calling \ref run(Node) "run()" or \ref init().
449 template <class H, class CR = typename Digraph::template NodeMap<int> >
450 struct SetStandardHeap
451 : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
452 typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> >
457 struct SetOperationTraitsTraits : public Traits {
458 typedef T OperationTraits;
461 /// \brief \ref named-templ-param "Named parameter" for setting
462 ///\c OperationTraits type
464 ///\ref named-templ-param "Named parameter" for setting
465 ///\ref OperationTraits type.
467 struct SetOperationTraits
468 : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
469 typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >
484 ///\param _g The digraph the algorithm runs on.
485 ///\param _length The length map used by the algorithm.
486 Dijkstra(const Digraph& _g, const LengthMap& _length) :
487 G(&_g), length(&_length),
488 _pred(NULL), local_pred(false),
489 _dist(NULL), local_dist(false),
490 _processed(NULL), local_processed(false),
491 _heap_cross_ref(NULL), local_heap_cross_ref(false),
492 _heap(NULL), local_heap(false)
498 if(local_pred) delete _pred;
499 if(local_dist) delete _dist;
500 if(local_processed) delete _processed;
501 if(local_heap_cross_ref) delete _heap_cross_ref;
502 if(local_heap) delete _heap;
505 ///Sets the length map.
507 ///Sets the length map.
508 ///\return <tt> (*this) </tt>
509 Dijkstra &lengthMap(const LengthMap &m)
515 ///Sets the map that stores the predecessor arcs.
517 ///Sets the map that stores the predecessor arcs.
518 ///If you don't use this function before calling \ref run(Node) "run()"
519 ///or \ref init(), an instance will be allocated automatically.
520 ///The destructor deallocates this automatically allocated map,
522 ///\return <tt> (*this) </tt>
523 Dijkstra &predMap(PredMap &m)
533 ///Sets the map that indicates which nodes are processed.
535 ///Sets the map that indicates which nodes are processed.
536 ///If you don't use this function before calling \ref run(Node) "run()"
537 ///or \ref init(), an instance will be allocated automatically.
538 ///The destructor deallocates this automatically allocated map,
540 ///\return <tt> (*this) </tt>
541 Dijkstra &processedMap(ProcessedMap &m)
543 if(local_processed) {
545 local_processed=false;
551 ///Sets the map that stores the distances of the nodes.
553 ///Sets the map that stores the distances of the nodes calculated by the
555 ///If you don't use this function before calling \ref run(Node) "run()"
556 ///or \ref init(), an instance will be allocated automatically.
557 ///The destructor deallocates this automatically allocated map,
559 ///\return <tt> (*this) </tt>
560 Dijkstra &distMap(DistMap &m)
570 ///Sets the heap and the cross reference used by algorithm.
572 ///Sets the heap and the cross reference used by algorithm.
573 ///If you don't use this function before calling \ref run(Node) "run()"
574 ///or \ref init(), heap and cross reference instances will be
575 ///allocated automatically.
576 ///The destructor deallocates these automatically allocated objects,
578 ///\return <tt> (*this) </tt>
579 Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
581 if(local_heap_cross_ref) {
582 delete _heap_cross_ref;
583 local_heap_cross_ref=false;
585 _heap_cross_ref = &cr;
596 void finalizeNodeData(Node v,Value dst)
598 _processed->set(v,true);
604 ///\name Execution Control
605 ///The simplest way to execute the %Dijkstra algorithm is to use
606 ///one of the member functions called \ref run(Node) "run()".\n
607 ///If you need more control on the execution, first you have to call
608 ///\ref init(), then you can add several source nodes with
609 ///\ref addSource(). Finally the actual path computation can be
610 ///performed with one of the \ref start() functions.
614 ///\brief Initializes the internal data structures.
616 ///Initializes the internal data structures.
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);
628 ///Adds a new source node.
630 ///Adds a new source node to the priority heap.
631 ///The optional second parameter is the initial distance of the node.
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())
638 if(_heap->state(s) != Heap::IN_HEAP) {
640 } else if(OperationTraits::less((*_heap)[s], dst)) {
642 _pred->set(s,INVALID);
646 ///Processes the next node in the priority heap
648 ///Processes the next node in the priority heap.
650 ///\return The processed node.
652 ///\warning The priority heap must not be empty.
653 Node processNextNode()
656 Value oldvalue=_heap->prio();
658 finalizeNodeData(v,oldvalue);
660 for(OutArcIt e(*G,v); e!=INVALID; ++e) {
662 switch(_heap->state(w)) {
664 _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
669 Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
670 if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
671 _heap->decrease(w, newvalue);
676 case Heap::POST_HEAP:
683 ///The next node to be processed.
685 ///Returns the next node to be processed or \c INVALID if the
686 ///priority heap is empty.
687 Node nextNode() const
689 return !_heap->empty()?_heap->top():INVALID;
692 ///Returns \c false if there are nodes to be processed.
694 ///Returns \c false if there are nodes to be processed
695 ///in the priority heap.
696 bool emptyQueue() const { return _heap->empty(); }
698 ///Returns the number of the nodes to be processed.
700 ///Returns the number of the nodes to be processed
701 ///in the priority heap.
702 int queueSize() const { return _heap->size(); }
704 ///Executes the algorithm.
706 ///Executes the algorithm.
708 ///This method runs the %Dijkstra algorithm from the root node(s)
709 ///in order to compute the shortest path to each node.
711 ///The algorithm computes
712 ///- the shortest path tree (forest),
713 ///- the distance of each node from the root(s).
715 ///\pre init() must be called and at least one root node should be
716 ///added with addSource() before using this function.
718 ///\note <tt>d.start()</tt> is just a shortcut of the following code.
720 /// while ( !d.emptyQueue() ) {
721 /// d.processNextNode();
726 while ( !emptyQueue() ) processNextNode();
729 ///Executes the algorithm until the given target node is processed.
731 ///Executes the algorithm until the given target node is processed.
733 ///This method runs the %Dijkstra algorithm from the root node(s)
734 ///in order to compute the shortest path to \c t.
736 ///The algorithm computes
737 ///- the shortest path to \c t,
738 ///- the distance of \c t from the root(s).
740 ///\pre init() must be called and at least one root node should be
741 ///added with addSource() before using this function.
744 while ( !_heap->empty() && _heap->top()!=t ) processNextNode();
745 if ( !_heap->empty() ) {
746 finalizeNodeData(_heap->top(),_heap->prio());
751 ///Executes the algorithm until a condition is met.
753 ///Executes the algorithm until a condition is met.
755 ///This method runs the %Dijkstra algorithm from the root node(s) in
756 ///order to compute the shortest path to a node \c v with
757 /// <tt>nm[v]</tt> true, if such a node can be found.
759 ///\param nm A \c bool (or convertible) node map. The algorithm
760 ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
762 ///\return The reached node \c v with <tt>nm[v]</tt> true or
763 ///\c INVALID if no such node was found.
765 ///\pre init() must be called and at least one root node should be
766 ///added with addSource() before using this function.
767 template<class NodeBoolMap>
768 Node start(const NodeBoolMap &nm)
770 while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
771 if ( _heap->empty() ) return INVALID;
772 finalizeNodeData(_heap->top(),_heap->prio());
776 ///Runs the algorithm from the given source node.
778 ///This method runs the %Dijkstra algorithm from node \c s
779 ///in order to compute the shortest path to each node.
781 ///The algorithm computes
782 ///- the shortest path tree,
783 ///- the distance of each node from the root.
785 ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
797 ///Finds the shortest path between \c s and \c t.
799 ///This method runs the %Dijkstra algorithm from node \c s
800 ///in order to compute the shortest path to node \c t
801 ///(it stops searching when \c t is processed).
803 ///\return \c true if \c t is reachable form \c s.
805 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
806 ///shortcut of the following code.
812 bool run(Node s,Node t) {
816 return (*_heap_cross_ref)[t] == Heap::POST_HEAP;
821 ///\name Query Functions
822 ///The results of the %Dijkstra algorithm can be obtained using these
824 ///Either \ref run(Node) "run()" or \ref start() should be called
825 ///before using them.
829 ///The shortest path to a node.
831 ///Returns the shortest path to a node.
833 ///\warning \c t should be reached from the root(s).
835 ///\pre Either \ref run(Node) "run()" or \ref init()
836 ///must be called before using this function.
837 Path path(Node t) const { return Path(*G, *_pred, t); }
839 ///The distance of a node from the root(s).
841 ///Returns the distance of a node from the root(s).
843 ///\warning If node \c v is not reached from the root(s), then
844 ///the return value of this function is undefined.
846 ///\pre Either \ref run(Node) "run()" or \ref init()
847 ///must be called before using this function.
848 Value dist(Node v) const { return (*_dist)[v]; }
850 ///Returns the 'previous arc' of the shortest path tree for a node.
852 ///This function returns the 'previous arc' of the shortest path
853 ///tree for the node \c v, i.e. it returns the last arc of a
854 ///shortest path from a root to \c v. It is \c INVALID if \c v
855 ///is not reached from the root(s) or if \c v is a root.
857 ///The shortest path tree used here is equal to the shortest path
858 ///tree used in \ref predNode().
860 ///\pre Either \ref run(Node) "run()" or \ref init()
861 ///must be called before using this function.
862 Arc predArc(Node v) const { return (*_pred)[v]; }
864 ///Returns the 'previous node' of the shortest path tree for a node.
866 ///This function returns the 'previous node' of the shortest path
867 ///tree for the node \c v, i.e. it returns the last but one node
868 ///from a shortest path from a root to \c v. It is \c INVALID
869 ///if \c v is not reached from the root(s) or if \c v is a root.
871 ///The shortest path tree used here is equal to the shortest path
872 ///tree used in \ref predArc().
874 ///\pre Either \ref run(Node) "run()" or \ref init()
875 ///must be called before using this function.
876 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
877 G->source((*_pred)[v]); }
879 ///\brief Returns a const reference to the node map that stores the
880 ///distances of the nodes.
882 ///Returns a const reference to the node map that stores the distances
883 ///of the nodes calculated by the algorithm.
885 ///\pre Either \ref run(Node) "run()" or \ref init()
886 ///must be called before using this function.
887 const DistMap &distMap() const { return *_dist;}
889 ///\brief Returns a const reference to the node map that stores the
892 ///Returns a const reference to the node map that stores the predecessor
893 ///arcs, which form the shortest path tree.
895 ///\pre Either \ref run(Node) "run()" or \ref init()
896 ///must be called before using this function.
897 const PredMap &predMap() const { return *_pred;}
899 ///Checks if a node is reached from the root(s).
901 ///Returns \c true if \c v is reached from the root(s).
903 ///\pre Either \ref run(Node) "run()" or \ref init()
904 ///must be called before using this function.
905 bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
908 ///Checks if a node is processed.
910 ///Returns \c true if \c v is processed, i.e. the shortest
911 ///path to \c v has already found.
913 ///\pre Either \ref run(Node) "run()" or \ref init()
914 ///must be called before using this function.
915 bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
918 ///The current distance of a node from the root(s).
920 ///Returns the current distance of a node from the root(s).
921 ///It may be decreased in the following processes.
923 ///\pre Either \ref run(Node) "run()" or \ref init()
924 ///must be called before using this function and
925 ///node \c v must be reached but not necessarily processed.
926 Value currentDist(Node v) const {
927 return processed(v) ? (*_dist)[v] : (*_heap)[v];
934 ///Default traits class of dijkstra() function.
936 ///Default traits class of dijkstra() function.
937 ///\tparam GR The type of the digraph.
938 ///\tparam LM The type of the length map.
939 template<class GR, class LM>
940 struct DijkstraWizardDefaultTraits
942 ///The type of the digraph the algorithm runs on.
944 ///The type of the map that stores the arc lengths.
946 ///The type of the map that stores the arc lengths.
947 ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
948 typedef LM LengthMap;
949 ///The type of the length of the arcs.
950 typedef typename LM::Value Value;
952 /// Operation traits for Dijkstra algorithm.
954 /// This class defines the operations that are used in the algorithm.
955 /// \see DijkstraDefaultOperationTraits
956 typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
958 /// The cross reference type used by the heap.
960 /// The cross reference type used by the heap.
961 /// Usually it is \c Digraph::NodeMap<int>.
962 typedef typename Digraph::template NodeMap<int> HeapCrossRef;
963 ///Instantiates a \ref HeapCrossRef.
965 ///This function instantiates a \ref HeapCrossRef.
966 /// \param g is the digraph, to which we would like to define the
968 static HeapCrossRef *createHeapCrossRef(const Digraph &g)
970 return new HeapCrossRef(g);
973 ///The heap type used by the Dijkstra algorithm.
975 ///The heap type used by the Dijkstra algorithm.
979 typedef BinHeap<Value, typename Digraph::template NodeMap<int>,
980 std::less<Value> > Heap;
982 ///Instantiates a \ref Heap.
984 ///This function instantiates a \ref Heap.
985 /// \param r is the HeapCrossRef which is used.
986 static Heap *createHeap(HeapCrossRef& r)
991 ///\brief The type of the map that stores the predecessor
992 ///arcs of the shortest paths.
994 ///The type of the map that stores the predecessor
995 ///arcs of the shortest paths.
996 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
997 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
998 ///Instantiates a PredMap.
1000 ///This function instantiates a PredMap.
1001 ///\param g is the digraph, to which we would like to define the
1003 static PredMap *createPredMap(const Digraph &g)
1005 return new PredMap(g);
1008 ///The type of the map that indicates which nodes are processed.
1010 ///The type of the map that indicates which nodes are processed.
1011 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1012 ///By default it is a NullMap.
1013 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1014 ///Instantiates a ProcessedMap.
1016 ///This function instantiates a ProcessedMap.
1017 ///\param g is the digraph, to which
1018 ///we would like to define the ProcessedMap.
1020 static ProcessedMap *createProcessedMap(const Digraph &g)
1022 static ProcessedMap *createProcessedMap(const Digraph &)
1025 return new ProcessedMap();
1028 ///The type of the map that stores the distances of the nodes.
1030 ///The type of the map that stores the distances of the nodes.
1031 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1032 typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
1033 ///Instantiates a DistMap.
1035 ///This function instantiates a DistMap.
1036 ///\param g is the digraph, to which we would like to define
1038 static DistMap *createDistMap(const Digraph &g)
1040 return new DistMap(g);
1043 ///The type of the shortest paths.
1045 ///The type of the shortest paths.
1046 ///It must meet the \ref concepts::Path "Path" concept.
1047 typedef lemon::Path<Digraph> Path;
1050 /// Default traits class used by DijkstraWizard
1052 /// To make it easier to use Dijkstra algorithm
1053 /// we have created a wizard class.
1054 /// This \ref DijkstraWizard class needs default traits,
1055 /// as well as the \ref Dijkstra class.
1056 /// The \ref DijkstraWizardBase is a class to be the default traits of the
1057 /// \ref DijkstraWizard class.
1058 template<class GR,class LM>
1059 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
1061 typedef DijkstraWizardDefaultTraits<GR,LM> Base;
1063 //The type of the nodes in the digraph.
1064 typedef typename Base::Digraph::Node Node;
1066 //Pointer to the digraph the algorithm runs on.
1068 //Pointer to the length map.
1070 //Pointer to the map of processed nodes.
1072 //Pointer to the map of predecessors arcs.
1074 //Pointer to the map of distances.
1076 //Pointer to the shortest path to the target node.
1078 //Pointer to the distance of the target node.
1084 /// This constructor does not require parameters, therefore it initiates
1085 /// all of the attributes to \c 0.
1086 DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
1087 _dist(0), _path(0), _di(0) {}
1091 /// This constructor requires two parameters,
1092 /// others are initiated to \c 0.
1093 /// \param g The digraph the algorithm runs on.
1094 /// \param l The length map.
1095 DijkstraWizardBase(const GR &g,const LM &l) :
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), _path(0), _di(0) {}
1102 /// Auxiliary class for the function-type interface of Dijkstra algorithm.
1104 /// This auxiliary class is created to implement the
1105 /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
1106 /// It does not have own \ref run(Node) "run()" method, it uses the
1107 /// functions and features of the plain \ref Dijkstra.
1109 /// This class should only be used through the \ref dijkstra() function,
1110 /// which makes it easier to use the algorithm.
1112 class DijkstraWizard : public TR
1116 ///The type of the digraph the algorithm runs on.
1117 typedef typename TR::Digraph Digraph;
1119 typedef typename Digraph::Node Node;
1120 typedef typename Digraph::NodeIt NodeIt;
1121 typedef typename Digraph::Arc Arc;
1122 typedef typename Digraph::OutArcIt OutArcIt;
1124 ///The type of the map that stores the arc lengths.
1125 typedef typename TR::LengthMap LengthMap;
1126 ///The type of the length of the arcs.
1127 typedef typename LengthMap::Value Value;
1128 ///\brief The type of the map that stores the predecessor
1129 ///arcs of the shortest paths.
1130 typedef typename TR::PredMap PredMap;
1131 ///The type of the map that stores the distances of the nodes.
1132 typedef typename TR::DistMap DistMap;
1133 ///The type of the map that indicates which nodes are processed.
1134 typedef typename TR::ProcessedMap ProcessedMap;
1135 ///The type of the shortest paths
1136 typedef typename TR::Path Path;
1137 ///The heap type used by the dijkstra algorithm.
1138 typedef typename TR::Heap Heap;
1143 DijkstraWizard() : TR() {}
1145 /// Constructor that requires parameters.
1147 /// Constructor that requires parameters.
1148 /// These parameters will be the default values for the traits class.
1149 /// \param g The digraph the algorithm runs on.
1150 /// \param l The length map.
1151 DijkstraWizard(const Digraph &g, const LengthMap &l) :
1155 DijkstraWizard(const TR &b) : TR(b) {}
1157 ~DijkstraWizard() {}
1159 ///Runs Dijkstra algorithm from the given source node.
1161 ///This method runs %Dijkstra algorithm from the given source node
1162 ///in order to compute the shortest path to each node.
1165 Dijkstra<Digraph,LengthMap,TR>
1166 dijk(*reinterpret_cast<const Digraph*>(Base::_g),
1167 *reinterpret_cast<const LengthMap*>(Base::_length));
1169 dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1171 dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1172 if (Base::_processed)
1173 dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1177 ///Finds the shortest path between \c s and \c t.
1179 ///This method runs the %Dijkstra algorithm from node \c s
1180 ///in order to compute the shortest path to node \c t
1181 ///(it stops searching when \c t is processed).
1183 ///\return \c true if \c t is reachable form \c s.
1184 bool run(Node s, Node t)
1186 Dijkstra<Digraph,LengthMap,TR>
1187 dijk(*reinterpret_cast<const Digraph*>(Base::_g),
1188 *reinterpret_cast<const LengthMap*>(Base::_length));
1190 dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1192 dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1193 if (Base::_processed)
1194 dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1197 *reinterpret_cast<Path*>(Base::_path) = dijk.path(t);
1199 *reinterpret_cast<Value*>(Base::_di) = dijk.dist(t);
1200 return dijk.reached(t);
1204 struct SetPredMapBase : public Base {
1206 static PredMap *createPredMap(const Digraph &) { return 0; };
1207 SetPredMapBase(const TR &b) : TR(b) {}
1209 ///\brief \ref named-func-param "Named parameter"
1210 ///for setting PredMap object.
1212 ///\ref named-func-param "Named parameter"
1213 ///for setting PredMap object.
1215 DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
1217 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1218 return DijkstraWizard<SetPredMapBase<T> >(*this);
1222 struct SetDistMapBase : public Base {
1224 static DistMap *createDistMap(const Digraph &) { return 0; };
1225 SetDistMapBase(const TR &b) : TR(b) {}
1227 ///\brief \ref named-func-param "Named parameter"
1228 ///for setting DistMap object.
1230 ///\ref named-func-param "Named parameter"
1231 ///for setting DistMap object.
1233 DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
1235 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1236 return DijkstraWizard<SetDistMapBase<T> >(*this);
1240 struct SetProcessedMapBase : public Base {
1241 typedef T ProcessedMap;
1242 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1243 SetProcessedMapBase(const TR &b) : TR(b) {}
1245 ///\brief \ref named-func-param "Named parameter"
1246 ///for setting ProcessedMap object.
1248 /// \ref named-func-param "Named parameter"
1249 ///for setting ProcessedMap object.
1251 DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1253 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1254 return DijkstraWizard<SetProcessedMapBase<T> >(*this);
1258 struct SetPathBase : public Base {
1260 SetPathBase(const TR &b) : TR(b) {}
1262 ///\brief \ref named-func-param "Named parameter"
1263 ///for getting the shortest path to the target node.
1265 ///\ref named-func-param "Named parameter"
1266 ///for getting the shortest path to the target node.
1268 DijkstraWizard<SetPathBase<T> > path(const T &t)
1270 Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
1271 return DijkstraWizard<SetPathBase<T> >(*this);
1274 ///\brief \ref named-func-param "Named parameter"
1275 ///for getting the distance of the target node.
1277 ///\ref named-func-param "Named parameter"
1278 ///for getting the distance of the target node.
1279 DijkstraWizard dist(const Value &d)
1281 Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
1287 ///Function-type interface for Dijkstra algorithm.
1289 /// \ingroup shortest_path
1290 ///Function-type interface for Dijkstra algorithm.
1292 ///This function also has several \ref named-func-param "named parameters",
1293 ///they are declared as the members of class \ref DijkstraWizard.
1294 ///The following examples show how to use these parameters.
1296 /// // Compute shortest path from node s to each node
1297 /// dijkstra(g,length).predMap(preds).distMap(dists).run(s);
1299 /// // Compute shortest path from s to t
1300 /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
1302 ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
1303 ///to the end of the parameter list.
1304 ///\sa DijkstraWizard
1306 template<class GR, class LM>
1307 DijkstraWizard<DijkstraWizardBase<GR,LM> >
1308 dijkstra(const GR &digraph, const LM &length)
1310 return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
1313 } //END OF NAMESPACE LEMON