2 * lemon/belmann_ford.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_BELMANN_FORD_H
18 #define LEMON_BELMANN_FORD_H
22 /// \brief BelmannFord algorithm.
25 #include <lemon/list_graph.h>
26 #include <lemon/invalid.h>
27 #include <lemon/error.h>
28 #include <lemon/maps.h>
34 /// \brief Default OperationTraits for the BelmannFord algorithm class.
36 /// It defines all computational operations and constants which are
37 /// used in the belmann ford algorithm. The default implementation
38 /// is based on the numeric_limits class. If the numeric type does not
39 /// have infinity value then the maximum value is used as extremal
43 bool has_infinity = std::numeric_limits<Value>::has_infinity>
44 struct BelmannFordDefaultOperationTraits {
45 /// \brief Gives back the zero value of the type.
47 return static_cast<Value>(0);
49 /// \brief Gives back the positive infinity value of the type.
50 static Value infinity() {
51 return std::numeric_limits<Value>::infinity();
53 /// \brief Gives back the sum of the given two elements.
54 static Value plus(const Value& left, const Value& right) {
57 /// \brief Gives back true only if the first value less than the second.
58 static bool less(const Value& left, const Value& right) {
63 template <typename Value>
64 struct BelmannFordDefaultOperationTraits<Value, false> {
66 return static_cast<Value>(0);
68 static Value infinity() {
69 return std::numeric_limits<Value>::max();
71 static Value plus(const Value& left, const Value& right) {
72 if (left == infinity() || right == infinity()) return infinity();
75 static bool less(const Value& left, const Value& right) {
80 /// \brief Default traits class of BelmannFord class.
82 /// Default traits class of BelmannFord class.
83 /// \param _Graph Graph type.
84 /// \param _LegthMap Type of length map.
85 template<class _Graph, class _LengthMap>
86 struct BelmannFordDefaultTraits {
87 /// The graph type the algorithm runs on.
90 /// \brief The type of the map that stores the edge lengths.
92 /// The type of the map that stores the edge lengths.
93 /// It must meet the \ref concept::ReadMap "ReadMap" concept.
94 typedef _LengthMap LengthMap;
96 // The type of the length of the edges.
97 typedef typename _LengthMap::Value Value;
99 /// \brief Operation traits for belmann-ford algorithm.
101 /// It defines the infinity type on the given Value type
102 /// and the used operation.
103 /// \see BelmannFordDefaultOperationTraits
104 typedef BelmannFordDefaultOperationTraits<Value> OperationTraits;
106 /// \brief The type of the map that stores the last edges of the
109 /// The type of the map that stores the last
110 /// edges of the shortest paths.
111 /// It must meet the \ref concept::WriteMap "WriteMap" concept.
113 typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
115 /// \brief Instantiates a PredMap.
117 /// This function instantiates a \ref PredMap.
118 /// \param G is the graph, to which we would like to define the PredMap.
119 /// \todo The graph alone may be insufficient for the initialization
120 static PredMap *createPredMap(const _Graph& graph) {
121 return new PredMap(graph);
124 /// \brief The type of the map that stores the dists of the nodes.
126 /// The type of the map that stores the dists of the nodes.
127 /// It must meet the \ref concept::WriteMap "WriteMap" concept.
129 typedef typename Graph::template NodeMap<typename _LengthMap::Value>
132 /// \brief Instantiates a DistMap.
134 /// This function instantiates a \ref DistMap.
135 /// \param G is the graph, to which we would like to define the
137 static DistMap *createDistMap(const _Graph& graph) {
138 return new DistMap(graph);
143 /// \brief %BelmannFord algorithm class.
145 /// \ingroup flowalgs
146 /// This class provides an efficient implementation of \c Belmann-Ford
147 /// algorithm. The edge lengths are passed to the algorithm using a
148 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
151 /// The Belmann-Ford algorithm solves the shortest path from one node
152 /// problem when the edges can have negative length but the graph should
153 /// not contain cycles with negative sum of length. If we can assume
154 /// that all edge is non-negative in the graph then the dijkstra algorithm
155 /// should be used rather.
157 /// The complexity of the algorithm is O(n * e).
159 /// The type of the length is determined by the
160 /// \ref concept::ReadMap::Value "Value" of the length map.
162 /// \param _Graph The graph type the algorithm runs on. The default value
163 /// is \ref ListGraph. The value of _Graph is not used directly by
164 /// BelmannFord, it is only passed to \ref BelmannFordDefaultTraits.
165 /// \param _LengthMap This read-only EdgeMap determines the lengths of the
166 /// edges. The default map type is \ref concept::StaticGraph::EdgeMap
167 /// "Graph::EdgeMap<int>". The value of _LengthMap is not used directly
168 /// by BelmannFord, it is only passed to \ref BelmannFordDefaultTraits.
169 /// \param _Traits Traits class to set various data types used by the
170 /// algorithm. The default traits class is \ref BelmannFordDefaultTraits
171 /// "BelmannFordDefaultTraits<_Graph,_LengthMap>". See \ref
172 /// BelmannFordDefaultTraits for the documentation of a BelmannFord traits
175 /// \author Balazs Dezso
178 template <typename _Graph, typename _LengthMap, typename _Traits>
180 template <typename _Graph=ListGraph,
181 typename _LengthMap=typename _Graph::template EdgeMap<int>,
182 typename _Traits=BelmannFordDefaultTraits<_Graph,_LengthMap> >
187 /// \brief \ref Exception for uninitialized parameters.
189 /// This error represents problems in the initialization
190 /// of the parameters of the algorithms.
192 class UninitializedParameter : public lemon::UninitializedParameter {
194 virtual const char* exceptionName() const {
195 return "lemon::BelmannFord::UninitializedParameter";
199 typedef _Traits Traits;
200 ///The type of the underlying graph.
201 typedef typename _Traits::Graph Graph;
203 typedef typename Graph::Node Node;
204 typedef typename Graph::NodeIt NodeIt;
205 typedef typename Graph::Edge Edge;
206 typedef typename Graph::EdgeIt EdgeIt;
208 /// \brief The type of the length of the edges.
209 typedef typename _Traits::LengthMap::Value Value;
210 /// \brief The type of the map that stores the edge lengths.
211 typedef typename _Traits::LengthMap LengthMap;
212 /// \brief The type of the map that stores the last
213 /// edges of the shortest paths.
214 typedef typename _Traits::PredMap PredMap;
215 /// \brief The type of the map that stores the dists of the nodes.
216 typedef typename _Traits::DistMap DistMap;
217 /// \brief The operation traits.
218 typedef typename _Traits::OperationTraits OperationTraits;
220 /// Pointer to the underlying graph.
222 /// Pointer to the length map
223 const LengthMap *length;
224 ///Pointer to the map of predecessors edges.
226 ///Indicates if \ref _pred is locally allocated (\c true) or not.
228 ///Pointer to the map of distances.
230 ///Indicates if \ref _dist is locally allocated (\c true) or not.
233 /// Creates the maps if necessary.
237 _pred = Traits::createPredMap(*graph);
241 _dist = Traits::createDistMap(*graph);
247 typedef BelmannFord Create;
249 /// \name Named template parameters
254 struct DefPredMapTraits : public Traits {
256 static PredMap *createPredMap(const Graph&) {
257 throw UninitializedParameter();
261 /// \brief \ref named-templ-param "Named parameter" for setting PredMap
263 /// \ref named-templ-param "Named parameter" for setting PredMap type
267 typedef BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > Create;
271 struct DefDistMapTraits : public Traits {
273 static DistMap *createDistMap(const Graph& graph) {
274 throw UninitializedParameter();
278 /// \brief \ref named-templ-param "Named parameter" for setting DistMap
281 /// \ref named-templ-param "Named parameter" for setting DistMap type
285 : public BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > {
286 typedef BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > Create;
290 struct DefOperationTraitsTraits : public Traits {
291 typedef T OperationTraits;
294 /// \brief \ref named-templ-param "Named parameter" for setting
295 /// OperationTraits type
297 /// \ref named-templ-param "Named parameter" for setting OperationTraits
300 struct DefOperationTraits
301 : public BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {
302 typedef BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> >
314 /// \brief Constructor.
316 /// \param _graph the graph the algorithm will run on.
317 /// \param _length the length map used by the algorithm.
318 BelmannFord(const Graph& _graph, const LengthMap& _length) :
319 graph(&_graph), length(&_length),
320 _pred(0), local_pred(false),
321 _dist(0), local_dist(false) {}
325 if(local_pred) delete _pred;
326 if(local_dist) delete _dist;
329 /// \brief Sets the length map.
331 /// Sets the length map.
332 /// \return \c (*this)
333 BelmannFord &lengthMap(const LengthMap &m) {
338 /// \brief Sets the map storing the predecessor edges.
340 /// Sets the map storing the predecessor edges.
341 /// If you don't use this function before calling \ref run(),
342 /// it will allocate one. The destuctor deallocates this
343 /// automatically allocated map, of course.
344 /// \return \c (*this)
345 BelmannFord &predMap(PredMap &m) {
354 /// \brief Sets the map storing the distances calculated by the algorithm.
356 /// Sets the map storing the distances calculated by the algorithm.
357 /// If you don't use this function before calling \ref run(),
358 /// it will allocate one. The destuctor deallocates this
359 /// automatically allocated map, of course.
360 /// \return \c (*this)
361 BelmannFord &distMap(DistMap &m) {
370 /// \name Execution control
371 /// The simplest way to execute the algorithm is to use
372 /// one of the member functions called \c run(...).
374 /// If you need more control on the execution,
375 /// first you must call \ref init(), then you can add several source nodes
376 /// with \ref addSource().
377 /// Finally \ref start() will perform the actual path
382 /// \brief Initializes the internal data structures.
384 /// Initializes the internal data structures.
385 void init(const Value value = OperationTraits::infinity()) {
387 for (NodeIt it(*graph); it != INVALID; ++it) {
388 _pred->set(it, INVALID);
389 _dist->set(it, value);
393 /// \brief Adds a new source node.
395 /// The optional second parameter is the initial distance of the node.
396 /// It just sets the distance of the node to the given value.
397 void addSource(Node source, Value dst = OperationTraits::zero()) {
398 _dist->set(source, dst);
401 /// \brief Executes the algorithm.
403 /// \pre init() must be called and at least one node should be added
404 /// with addSource() before using this function.
406 /// This method runs the %BelmannFord algorithm from the root node(s)
407 /// in order to compute the shortest path to each node. The algorithm
409 /// - The shortest path tree.
410 /// - The distance of each node from the root(s).
412 int num = countNodes(*graph) - 1;
413 for (int i = 0; i < num; ++i) {
415 for (EdgeIt it(*graph); it != INVALID; ++it) {
416 Node source = graph->source(it);
417 Node target = graph->target(it);
419 OperationTraits::plus((*_dist)[source], (*length)[it]);
420 if (OperationTraits::less(relaxed, (*_dist)[target])) {
421 _pred->set(target, it);
422 _dist->set(target, relaxed);
430 /// \brief Executes the algorithm and checks the negative cycles.
432 /// \pre init() must be called and at least one node should be added
433 /// with addSource() before using this function. If there is
434 /// a negative cycles in the graph it gives back false.
436 /// This method runs the %BelmannFord algorithm from the root node(s)
437 /// in order to compute the shortest path to each node. The algorithm
439 /// - The shortest path tree.
440 /// - The distance of each node from the root(s).
441 bool checkedStart() {
442 int num = countNodes(*graph);
443 for (int i = 0; i < num; ++i) {
445 for (EdgeIt it(*graph); it != INVALID; ++it) {
446 Node source = graph->source(it);
447 Node target = graph->target(it);
449 OperationTraits::plus((*_dist)[source], (*length)[it]);
450 if (OperationTraits::less(relaxed, (*_dist)[target])) {
451 _pred->set(target, it);
452 _dist->set(target, relaxed);
456 if (done) return true;
461 /// \brief Runs %BelmannFord algorithm from node \c s.
463 /// This method runs the %BelmannFord algorithm from a root node \c s
464 /// in order to compute the shortest path to each node. The algorithm
466 /// - The shortest path tree.
467 /// - The distance of each node from the root.
469 /// \note d.run(s) is just a shortcut of the following code.
483 /// \name Query Functions
484 /// The result of the %BelmannFord algorithm can be obtained using these
486 /// Before the use of these functions,
487 /// either run() or start() must be called.
491 /// \brief Copies the shortest path to \c t into \c p
493 /// This function copies the shortest path to \c t into \c p.
494 /// If it \c t is a source itself or unreachable, then it does not
497 /// \return Returns \c true if a path to \c t was actually copied to \c p,
498 /// \c false otherwise.
500 template <typename Path>
501 bool getPath(Path &p, Node t) {
504 typename Path::Builder b(p);
505 for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
506 b.pushFront(predEdge(t));
513 /// \brief The distance of a node from the root.
515 /// Returns the distance of a node from the root.
516 /// \pre \ref run() must be called before using this function.
517 /// \warning If node \c v in unreachable from the root the return value
518 /// of this funcion is undefined.
519 Value dist(Node v) const { return (*_dist)[v]; }
521 /// \brief Returns the 'previous edge' of the shortest path tree.
523 /// For a node \c v it returns the 'previous edge' of the shortest path
524 /// tree, i.e. it returns the last edge of a shortest path from the root
525 /// to \c v. It is \ref INVALID if \c v is unreachable from the root or
526 /// if \c v=s. The shortest path tree used here is equal to the shortest
527 /// path tree used in \ref predNode().
528 /// \pre \ref run() must be called before using
530 Edge predEdge(Node v) const { return (*_pred)[v]; }
532 /// \brief Returns the 'previous node' of the shortest path tree.
534 /// For a node \c v it returns the 'previous node' of the shortest path
535 /// tree, i.e. it returns the last but one node from a shortest path from
536 /// the root to \c /v. It is INVALID if \c v is unreachable from the root
537 /// or if \c v=s. The shortest path tree used here is equal to the
538 /// shortest path tree used in \ref predEdge(). \pre \ref run() must be
539 /// called before using this function.
540 Node predNode(Node v) const {
541 return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]);
544 /// \brief Returns a reference to the NodeMap of distances.
546 /// Returns a reference to the NodeMap of distances. \pre \ref run() must
547 /// be called before using this function.
548 const DistMap &distMap() const { return *_dist;}
550 /// \brief Returns a reference to the shortest path tree map.
552 /// Returns a reference to the NodeMap of the edges of the
553 /// shortest path tree.
554 /// \pre \ref run() must be called before using this function.
555 const PredMap &predMap() const { return *_pred; }
557 /// \brief Checks if a node is reachable from the root.
559 /// Returns \c true if \c v is reachable from the root.
560 /// \pre \ref run() must be called before using this function.
562 bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
567 /// \brief Default traits class of BelmannFord function.
569 /// Default traits class of BelmannFord function.
570 /// \param _Graph Graph type.
571 /// \param _LengthMap Type of length map.
572 template <typename _Graph, typename _LengthMap>
573 struct BelmannFordWizardDefaultTraits {
574 /// \brief The graph type the algorithm runs on.
575 typedef _Graph Graph;
577 /// \brief The type of the map that stores the edge lengths.
579 /// The type of the map that stores the edge lengths.
580 /// It must meet the \ref concept::ReadMap "ReadMap" concept.
581 typedef _LengthMap LengthMap;
583 /// \brief The value type of the length map.
584 typedef typename _LengthMap::Value Value;
586 /// \brief Operation traits for belmann-ford algorithm.
588 /// It defines the infinity type on the given Value type
589 /// and the used operation.
590 /// \see BelmannFordDefaultOperationTraits
591 typedef BelmannFordDefaultOperationTraits<Value> OperationTraits;
593 /// \brief The type of the map that stores the last
594 /// edges of the shortest paths.
596 /// The type of the map that stores the last
597 /// edges of the shortest paths.
598 /// It must meet the \ref concept::WriteMap "WriteMap" concept.
599 typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap;
601 /// \brief Instantiates a PredMap.
603 /// This function instantiates a \ref PredMap.
604 static PredMap *createPredMap(const _Graph &) {
605 return new PredMap();
607 /// \brief The type of the map that stores the dists of the nodes.
609 /// The type of the map that stores the dists of the nodes.
610 /// It must meet the \ref concept::WriteMap "WriteMap" concept.
611 typedef NullMap<typename Graph::Node, Value> DistMap;
612 /// \brief Instantiates a DistMap.
614 /// This function instantiates a \ref DistMap.
615 static DistMap *createDistMap(const _Graph &) {
616 return new DistMap();
620 /// \brief Default traits used by \ref BelmannFordWizard
622 /// To make it easier to use BelmannFord algorithm
623 /// we have created a wizard class.
624 /// This \ref BelmannFordWizard class needs default traits,
625 /// as well as the \ref BelmannFord class.
626 /// The \ref BelmannFordWizardBase is a class to be the default traits of the
627 /// \ref BelmannFordWizard class.
628 /// \todo More named parameters are required...
629 template<class _Graph,class _LengthMap>
630 class BelmannFordWizardBase
631 : public BelmannFordWizardDefaultTraits<_Graph,_LengthMap> {
633 typedef BelmannFordWizardDefaultTraits<_Graph,_LengthMap> Base;
635 /// Type of the nodes in the graph.
636 typedef typename Base::Graph::Node Node;
638 /// Pointer to the underlying graph.
640 /// Pointer to the length map
642 ///Pointer to the map of predecessors edges.
644 ///Pointer to the map of distances.
646 ///Pointer to the source node.
652 /// This constructor does not require parameters, therefore it initiates
653 /// all of the attributes to default values (0, INVALID).
654 BelmannFordWizardBase() : _graph(0), _length(0), _pred(0),
655 _dist(0), _source(INVALID) {}
659 /// This constructor requires some parameters,
660 /// listed in the parameters list.
661 /// Others are initiated to 0.
662 /// \param graph is the initial value of \ref _graph
663 /// \param length is the initial value of \ref _length
664 /// \param source is the initial value of \ref _source
665 BelmannFordWizardBase(const _Graph& graph,
666 const _LengthMap& length,
667 Node source = INVALID) :
668 _graph((void *)&graph), _length((void *)&length), _pred(0),
669 _dist(0), _source(source) {}
673 /// A class to make the usage of BelmannFord algorithm easier
675 /// This class is created to make it easier to use BelmannFord algorithm.
676 /// It uses the functions and features of the plain \ref BelmannFord,
677 /// but it is much simpler to use it.
679 /// Simplicity means that the way to change the types defined
680 /// in the traits class is based on functions that returns the new class
681 /// and not on templatable built-in classes.
682 /// When using the plain \ref BelmannFord
683 /// the new class with the modified type comes from
684 /// the original class by using the ::
685 /// operator. In the case of \ref BelmannFordWizard only
686 /// a function have to be called and it will
687 /// return the needed class.
689 /// It does not have own \ref run method. When its \ref run method is called
690 /// it initiates a plain \ref BelmannFord class, and calls the \ref
691 /// BelmannFord::run method of it.
692 template<class _Traits>
693 class BelmannFordWizard : public _Traits {
694 typedef _Traits Base;
696 ///The type of the underlying graph.
697 typedef typename _Traits::Graph Graph;
699 typedef typename Graph::Node Node;
700 typedef typename Graph::NodeIt NodeIt;
701 typedef typename Graph::Edge Edge;
702 typedef typename Graph::OutEdgeIt EdgeIt;
704 ///The type of the map that stores the edge lengths.
705 typedef typename _Traits::LengthMap LengthMap;
707 ///The type of the length of the edges.
708 typedef typename LengthMap::Value Value;
710 ///\brief The type of the map that stores the last
711 ///edges of the shortest paths.
712 typedef typename _Traits::PredMap PredMap;
714 ///The type of the map that stores the dists of the nodes.
715 typedef typename _Traits::DistMap DistMap;
719 BelmannFordWizard() : _Traits() {}
721 /// \brief Constructor that requires parameters.
723 /// Constructor that requires parameters.
724 /// These parameters will be the default values for the traits class.
725 BelmannFordWizard(const Graph& graph, const LengthMap& length,
726 Node source = INVALID)
727 : _Traits(graph, length, source) {}
729 /// \brief Copy constructor
730 BelmannFordWizard(const _Traits &b) : _Traits(b) {}
732 ~BelmannFordWizard() {}
734 /// \brief Runs BelmannFord algorithm from a given node.
736 /// Runs BelmannFord algorithm from a given node.
737 /// The node can be given by the \ref source function.
739 if(Base::_source == INVALID) throw UninitializedParameter();
740 BelmannFord<Graph,LengthMap,_Traits>
741 bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length);
742 if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred);
743 if (Base::_dist) bf.distMap(*(DistMap*)Base::_dist);
744 bf.run(Base::_source);
747 /// \brief Runs BelmannFord algorithm from the given node.
749 /// Runs BelmannFord algorithm from the given node.
750 /// \param s is the given source.
751 void run(Node source) {
752 Base::_source = source;
757 struct DefPredMapBase : public Base {
759 static PredMap *createPredMap(const Graph &) { return 0; };
760 DefPredMapBase(const _Traits &b) : _Traits(b) {}
763 ///\brief \ref named-templ-param "Named parameter"
764 ///function for setting PredMap type
766 /// \ref named-templ-param "Named parameter"
767 ///function for setting PredMap type
770 BelmannFordWizard<DefPredMapBase<T> > predMap(const T &t)
772 Base::_pred=(void *)&t;
773 return BelmannFordWizard<DefPredMapBase<T> >(*this);
777 struct DefDistMapBase : public Base {
779 static DistMap *createDistMap(const Graph &) { return 0; };
780 DefDistMapBase(const _Traits &b) : _Traits(b) {}
783 ///\brief \ref named-templ-param "Named parameter"
784 ///function for setting DistMap type
786 /// \ref named-templ-param "Named parameter"
787 ///function for setting DistMap type
790 BelmannFordWizard<DefDistMapBase<T> > distMap(const T &t) {
791 Base::_dist=(void *)&t;
792 return BelmannFordWizard<DefDistMapBase<T> >(*this);
796 struct DefOperationTraitsBase : public Base {
797 typedef T OperationTraits;
798 DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
801 ///\brief \ref named-templ-param "Named parameter"
802 ///function for setting OperationTraits type
804 /// \ref named-templ-param "Named parameter"
805 ///function for setting OperationTraits type
808 BelmannFordWizard<DefOperationTraitsBase<T> > distMap() {
809 return BelmannFordWizard<DefDistMapBase<T> >(*this);
812 /// \brief Sets the source node, from which the BelmannFord algorithm runs.
814 /// Sets the source node, from which the BelmannFord algorithm runs.
815 /// \param s is the source node.
816 BelmannFordWizard<_Traits>& source(Node source) {
817 Base::_source = source;
823 /// \brief Function type interface for BelmannFord algorithm.
825 /// \ingroup flowalgs
826 /// Function type interface for BelmannFord algorithm.
828 /// This function also has several \ref named-templ-func-param
829 /// "named parameters", they are declared as the members of class
830 /// \ref BelmannFordWizard.
832 /// example shows how to use these parameters.
834 /// belmannford(g,length,source).predMap(preds).run();
836 /// \warning Don't forget to put the \ref BelmannFordWizard::run() "run()"
837 /// to the end of the parameter list.
838 /// \sa BelmannFordWizard
840 template<class _Graph, class _LengthMap>
841 BelmannFordWizard<BelmannFordWizardBase<_Graph,_LengthMap> >
842 belmannFord(const _Graph& graph,
843 const _LengthMap& length,
844 typename _Graph::Node source = INVALID) {
845 return BelmannFordWizard<BelmannFordWizardBase<_Graph,_LengthMap> >
846 (graph, length, source);
849 } //END OF NAMESPACE LEMON