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
-
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. |
|
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.
|
|
|
| BellmanFord (const Digraph &g, const LengthMap &length) |
| Constructor.
|
|
| ~BellmanFord () |
| Destructor.
|
|
BellmanFord & | lengthMap (const LengthMap &map) |
| Sets the length map.
|
|
BellmanFord & | predMap (PredMap &map) |
| Sets the map that stores the predecessor arcs.
|
|
BellmanFord & | distMap (DistMap &map) |
| Sets the map that stores the distances of the nodes.
|
|
|
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.
|
|
|
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 DistMap & | distMap () const |
| Returns a const reference to the node map that stores the distances of the nodes.
|
|
const PredMap & | predMap () 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< Digraph > | negativeCycle () const |
| Gives back a negative cycle.
|
|