BellmanFord

Declared in lemon/bellman_ford.h, in the group Shortest Path Algorithms; the same class on the Doxygen site.

template< typename GR , typename LEN , typename TR >
class BellmanFord

BellmanFord algorithm class.

This class provides an efficient implementation of the Bellman-Ford algorithm. The maximum time complexity of the algorithm is O(nm).

The Bellman-Ford algorithm solves the single-source shortest path problem when the arcs can have negative lengths, but the digraph should not contain directed cycles with negative total length. If all arc costs are non-negative, consider to use the Dijkstra algorithm instead, since it is more efficient.

The arc lengths are passed to the algorithm using a ReadMap, so it is easy to change it to any kind of length. The type of the length values is determined by the Value type of the length map.

There is also a function-type interface for the Bellman-Ford algorithm, which is convenient in the simplier cases and it can be used easier.

Template Parameters:
  • GR – The type of the digraph the algorithm runs on. The default type is ListDigraph.

  • LEN – A readable arc map that specifies the lengths of the arcs. The default map type is GR::ArcMap< int >.

  • TR – The traits class that defines various types used by the algorithm. By default, it is BellmanFordDefaultTraits< GR , LEN >. In most cases, this parameter should not be set directly, consider to use the named template parameters instead.

Execution Control

The simplest way to execute the Bellman-Ford algorithm is to use one of the member functions called .\n If you need better control on the execution, you have to call init() first, then you can add several source nodes with addSource(). Finally the actual path computation can be performed with start(), checkedStart() or limitedStart().

inline void init( const Value value = OperationTraits::infinity() )

Initializes the internal data structures. The optional parameter is the initial distance of each node.

inline void addSource( Node source , Value dst = OperationTraits::zero() )

Adds a new source node.

This function adds a new source node. The optional second parameter is the initial distance of the node.

inline bool processNextRound()

Executes one round from the Bellman-Ford algorithm.

If the algoritm calculated the distances in the previous round exactly for the paths of at most k arcs, then this function will calculate the distances exactly for the paths of at most k+1 arcs. Performing k iterations using this function calculates the shortest path distances exactly for the paths consisting of at most k arcs.

See also

ActiveIt

Warning

The paths with limited arc number cannot be retrieved easily with path() or predArc() functions. If you also need the shortest paths and not only the distances, you should store the predecessor map after each iteration and build the path manually.

Returns:

true when the algorithm have not found more shorter paths.

inline bool processNextWeakRound()

Executes one weak round from the Bellman-Ford algorithm.

If the algorithm calculated the distances in the previous round at least for the paths of at most k arcs, then this function will calculate the distances at least for the paths of at most k+1 arcs. This function does not make it possible to calculate the shortest path distances exactly for paths consisting of at most k arcs, this is why it is called weak round.

See also

ActiveIt

Returns:

true when the algorithm have not found more shorter paths.

inline void start()

Executes the algorithm.

This method runs the Bellman-Ford algorithm from the root node(s) in order to compute the shortest path to each node.

The algorithm computes

  • the shortest path tree (forest),

  • the distance of each node from the root(s).

Pre:

init() must be called and at least one root node should be added with addSource() before using this function.

inline bool checkedStart()

Executes the algorithm and checks the negative cycles.

This method runs the Bellman-Ford algorithm from the root node(s) in order to compute the shortest path to each node and also checks if the digraph contains cycles with negative total length.

The algorithm computes

  • the shortest path tree (forest),

  • the distance of each node from the root(s).

Returns:

false if there is a negative cycle in the digraph.

Pre:

init() must be called and at least one root node should be added with addSource() before using this function.

inline void limitedStart( int num )

Executes the algorithm with arc number limit.

This method runs the Bellman-Ford algorithm from the root node(s) in order to compute the shortest path distance for each node using only the paths consisting of at most num arcs.

The algorithm computes

  • the limited distance of each node from the root(s),

  • the predecessor arc for each node.

Warning

The paths with limited arc number cannot be retrieved easily with path() or predArc() functions. If you also need the shortest paths and not only the distances, you should store the predecessor map after each iteration and build the path manually.

Pre:

init() must be called and at least one root node should be added with addSource() before using this function.

inline void run( Node s )

Runs the algorithm from the given root node.

This method runs the Bellman-Ford algorithm from the given root node s in order to compute the shortest path to each node.

The algorithm computes

  • the shortest path tree (forest),

  • the distance of each node from the root(s).

Note

bf.run(s) is just a shortcut of the following code.

bf.init();
bf.addSource( s );
bf.start();

inline void run( Node s , int num )

Runs the algorithm from the given root node with arc number limit.

This method runs the Bellman-Ford algorithm from the given root node s in order to compute the shortest path distance for each node using only the paths consisting of at most num arcs.

The algorithm computes

  • the limited distance of each node from the root(s),

  • the predecessor arc for each node.

Note

bf.run(s, num) is just a shortcut of the following code.

bf.init();
bf.addSource( s );
bf.limitedStart( num );

Warning

The paths with limited arc number cannot be retrieved easily with path() or predArc() functions. If you also need the shortest paths and not only the distances, you should store the predecessor map after each iteration and build the path manually.

Query Functions

The result of the Bellman-Ford algorithm can be obtained using these functions.

Either

run() or init() should be called before using them.

inline Path path( Node t ) const

The shortest path to the given node.

Gives back the shortest path to the given node from the root(s).

Warning

t should be reached from the root(s).

Pre:

Either run() or init() must be called before using this function.

inline Value dist( Node v ) const

The distance of the given node from the root(s).

Returns the distance of the given node from the root(s).

Warning

If node v is not reached from the root(s), then the return value of this function is undefined.

Pre:

Either run() or init() must be called before using this function.

inline Arc predArc( Node v ) const

Returns the ‘previous arc’ of the shortest path tree for the given node.

This function returns the ‘previous arc’ of the shortest path tree for node v, i.e. it returns the last arc of a shortest path from a root to v. It is INVALID if v is not reached from the root(s) or if v is a root.

The shortest path tree used here is equal to the shortest path tree used in predNode() and predMap().

Pre:

Either run() or init() must be called before using this function.

inline Node predNode( Node v ) const

Returns the ‘previous node’ of the shortest path tree for the given node.

This function returns the ‘previous node’ of the shortest path tree for node v, i.e. it returns the last but one node of a shortest path from a root to v. It is INVALID if v is not reached from the root(s) or if v is a root.

The shortest path tree used here is equal to the shortest path tree used in predArc() and predMap().

Pre:

Either run() or init() must be called before using this function.

inline const DistMap & distMap() const

Returns a const reference to the node map that stores the distances of the nodes.

Returns a const reference to the node map that stores the distances of the nodes calculated by the algorithm.

Pre:

Either run() or init() must be called before using this function.

inline const PredMap & predMap() const

Returns a const reference to the node map that stores the predecessor arcs.

Returns a const reference to the node map that stores the predecessor arcs, which form the shortest path tree (forest).

Pre:

Either run() or init() must be called before using this function.

inline bool reached( Node v ) const

Checks if a node is reached from the root(s).

Returns true if v is reached from the root(s).

Pre:

Either run() or init() must be called before using this function.

inline lemon::Path< Digraph > negativeCycle() const

Gives back a negative cycle.

This function gives back a directed cycle with negative total length if the algorithm has already found one. Otherwise it gives back an empty path.

Public Types

typedef TR::Digraph Digraph

The type of the underlying digraph.

typedef TR::LengthMap::Value Value

The type of the arc lengths.

typedef TR::LengthMap LengthMap

The type of the map that stores the arc lengths.

typedef TR::PredMap PredMap

The type of the map that stores the last arcs of the shortest paths.

typedef TR::DistMap DistMap

The type of the map that stores the distances of the nodes.

typedef PredMapPath< Digraph , PredMap > Path

The type of the paths.

typedef TR::OperationTraits OperationTraits

The operation traits class of the algorithm.

typedef TR Traits

The traits class of the algorithm.

typedef BellmanFord Create

Public Functions

inline BellmanFord( const Digraph & g , const LengthMap & length )

Constructor.

Parameters:
  • g – The digraph the algorithm runs on.

  • length – The length map used by the algorithm.

inline ~BellmanFord()

Destructor.

inline BellmanFord & lengthMap( const LengthMap & map )

Sets the length map.

Returns:

(*this)

inline BellmanFord & operationTraits( const OperationTraits & ops )

Sets the object of the operation traits class.

The operations on the distances are those of an object of the operation traits class [see SetOperationTraits], default constructed unless one is given here, which lets them depend on the instance, e.g., on a tolerance of its own.

Returns:

(*this)

inline const OperationTraits & operationTraits() const

The object of the operation traits class in use.

inline BellmanFord & predMap( PredMap & map )

Sets the map that stores the predecessor arcs. If you don’t use this function before calling run() or init(), an instance will be allocated automatically. The destructor deallocates this automatically allocated map, of course.

Returns:

(*this)

inline BellmanFord & distMap( DistMap & map )

Sets the map that stores the distances of the nodes.

Sets the map that stores the distances of the nodes calculated by the algorithm. If you don’t use this function before calling run() or init(), an instance will be allocated automatically. The destructor deallocates this automatically allocated map, of course.

Returns:

(*this)

inline LemonRangeWrapper1< ActiveIt , BellmanFord > activeNodes() const

Gets the collection of the active nodes.

This function can be used for iterating on the active nodes of the Bellman-Ford algorithm after the last phase. These nodes should be checked in the next phase to find augmenting arcs outgoing from them. It returns a wrapped ActiveIt, which looks like an STL container (by having begin() and end()) which you can use in range-based for loops, STL algorithms, etc.

Protected Functions

inline BellmanFord()
template< class T >
struct SetPredMapTraits : public Traits

Public Types

typedef T PredMap

Public Static Functions

static inline PredMap * createPredMap( const Digraph & )
template< class T >
struct SetPredMap : public BellmanFord< Digraph , LengthMap , SetPredMapTraits< T > >

Named parameter for setting PredMap type. It must conform to the WriteMap concept.

Public Types

typedef BellmanFord< Digraph , LengthMap , SetPredMapTraits< T > > Create
template< class T >
struct SetDistMapTraits : public Traits

Public Types

typedef T DistMap

Public Static Functions

static inline DistMap * createDistMap( const Digraph & )
template< class T >
struct SetDistMap : public BellmanFord< Digraph , LengthMap , SetDistMapTraits< T > >

Named parameter for setting DistMap type. It must conform to the WriteMap concept.

Public Types

typedef BellmanFord< Digraph , LengthMap , SetDistMapTraits< T > > Create
template< class T >
struct SetOperationTraitsTraits : public Traits

Public Types

typedef T OperationTraits
template< class T >
struct SetOperationTraits : public BellmanFord< Digraph , LengthMap , SetOperationTraitsTraits< T > >

Named parameter for setting OperationTraits type. For more information, see BellmanFordDefaultOperationTraits.

Public Types

typedef BellmanFord< Digraph , LengthMap , SetOperationTraitsTraits< T > > Create
class ActiveIt

LEMON iterator for getting the active nodes.

This class provides a common style LEMON iterator that traverses the active nodes of the Bellman-Ford algorithm after the last phase. These nodes should be checked in the next phase to find augmenting arcs outgoing from them.

Public Functions

inline ActiveIt( const BellmanFord & algorithm )

Constructor.

Constructor for getting the active nodes of the given BellmanFord instance.

inline ActiveIt(Invalid)

Invalid constructor.

inline operator Node() const

Conversion to Node.

inline ActiveIt & operator++()

Increment operator.

inline bool operator==( const ActiveIt & it ) const
inline bool operator!=( const ActiveIt & it ) const
inline bool operator<( const ActiveIt & it ) const