All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
List of all members | Classes | Public Types | Public Member Functions
BellmanFord< GR, LEN, TR > Class Template Reference

Detailed Description

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

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

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
GRThe type of the digraph the algorithm runs on. The default type is ListDigraph.
LENA readable arc map that specifies the lengths of the arcs. The default map type is GR::ArcMap<int>.
TRThe 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.

#include <lemon/bellman_ford.h>

Classes

class  ActiveIt
 LEMON iterator for getting the active nodes. More...
 
struct  SetDistMap
 Named parameter for setting DistMap type. More...
 
struct  SetOperationTraits
 Named parameter for setting OperationTraits type. More...
 
struct  SetPredMap
 Named parameter for setting PredMap type. More...
 

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.
 

Public Member Functions

 BellmanFord (const Digraph &g, const LengthMap &length)
 Constructor.
 
 ~BellmanFord ()
 Destructor.
 
BellmanFordlengthMap (const LengthMap &map)
 Sets the length map.
 
BellmanFordpredMap (PredMap &map)
 Sets the map that stores the predecessor arcs.
 
BellmanForddistMap (DistMap &map)
 Sets the map that stores the distances of the nodes.
 
Execution Control

The simplest way to execute the Bellman-Ford algorithm is to use one of the member functions called run().
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().

void init (const Value value=OperationTraits::infinity())
 Initializes the internal data structures.
 
void addSource (Node source, Value dst=OperationTraits::zero())
 Adds a new source node.
 
bool processNextRound ()
 Executes one round from the Bellman-Ford algorithm.
 
bool processNextWeakRound ()
 Executes one weak round from the Bellman-Ford algorithm.
 
void start ()
 Executes the algorithm.
 
bool checkedStart ()
 Executes the algorithm and checks the negative cycles.
 
void limitedStart (int num)
 Executes the algorithm with arc number limit.
 
void run (Node s)
 Runs the algorithm from the given root node.
 
void run (Node s, int num)
 Runs the algorithm from the given root node with arc number limit.
 
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.

Path path (Node t) const
 The shortest path to the given node.
 
Value dist (Node v) const
 The distance of the given node from the root(s).
 
Arc predArc (Node v) const
 Returns the 'previous arc' of the shortest path tree for the given node.
 
Node predNode (Node v) const
 Returns the 'previous node' of the shortest path tree for the given node.
 
const DistMapdistMap () const
 Returns a const reference to the node map that stores the distances of the nodes.
 
const PredMappredMap () const
 Returns a const reference to the node map that stores the predecessor arcs.
 
bool reached (Node v) const
 Checks if a node is reached from the root(s).
 
lemon::Path< DigraphnegativeCycle () const
 Gives back a negative cycle.
 

Constructor & Destructor Documentation

BellmanFord ( const Digraph g,
const LengthMap length 
)
inline

Constructor.

Parameters
gThe digraph the algorithm runs on.
lengthThe length map used by the algorithm.

Member Function Documentation

BellmanFord& lengthMap ( const LengthMap map)
inline

Sets the length map.

Returns
(*this)
BellmanFord& predMap ( PredMap map)
inline

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)
BellmanFord& distMap ( DistMap map)
inline

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)
void init ( const Value  value = OperationTraits::infinity())
inline

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

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

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

bool processNextRound ( )
inline

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.

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.
See Also
ActiveIt
bool processNextWeakRound ( )
inline

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.

Returns
true when the algorithm have not found more shorter paths.
See Also
ActiveIt
void start ( )
inline

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).
Precondition
init() must be called and at least one root node should be added with addSource() before using this function.
bool checkedStart ( )
inline

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.
Precondition
init() must be called and at least one root node should be added with addSource() before using this function.
void limitedStart ( int  num)
inline

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.
Precondition
init() must be called and at least one root node should be added with addSource() before using this function.
void run ( Node  s)
inline

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();
void run ( Node  s,
int  num 
)
inline

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.
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.
Note
bf.run(s, num) is just a shortcut of the following code.
bf.init();
bf.addSource(s);
bf.limitedStart(num);
Path path ( Node  t) const
inline

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

Warning
t should be reached from the root(s).
Precondition
Either run() or init() must be called before using this function.
Value dist ( Node  v) const
inline

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.
Precondition
Either run() or init() must be called before using this function.
Arc predArc ( Node  v) const
inline

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().

Precondition
Either run() or init() must be called before using this function.
Node predNode ( Node  v) const
inline

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().

Precondition
Either run() or init() must be called before using this function.
const DistMap& distMap ( ) const
inline

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

Precondition
Either run() or init() must be called before using this function.
const PredMap& predMap ( ) const
inline

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

Precondition
Either run() or init() must be called before using this function.
bool reached ( Node  v) const
inline

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

Precondition
Either run() or init() must be called before using this function.
lemon::Path<Digraph> negativeCycle ( ) const
inline

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.