// named paramter version template <class EdgeListGraph, class Size, class P, class T, class R> bool bellman_ford_shortest_paths(EdgeListGraph& g, Size N, const bgl_named_params<P, T, R>& params = all defaults) // non-named parameter version template <class EdgeListGraph, class Size, class WeightMap, class PredecessorMap, class DistanceMap, class BinaryFunction, class BinaryPredicate, class BellmanFordVisitor> bool bellman_ford_shortest_paths(EdgeListGraph& g, Size N, WeightMap weight, PredecessorMap pred, DistanceMap distance, BinaryFunction combine, BinaryPredicate compare, BellmanFordVisitor v)
The Bellman-Ford algorithm [4,11,20,8] solves the single-source shortest paths problem for a graph with both positive and negative edge weights. For the definition of the shortest paths problem see Section Shortest-Paths Algorithms. If you only need to solve the shortest paths problem for positive edge weights, Dijkstra's algorithm provides a more efficient alternative. If all the edge weights are all equal to one then breadth-first search provides an even more efficient alternative.
Before calling the bellman_ford_shortest_paths() function, the user must assign the source vertex a distance of zero and all other vertices a distance of infinity. The Bellman-Ford algorithm proceeds by looping through all of the edges in the graph, applying the relaxation operation to each edge. In the following pseudo-code, v is a vertex adjacent to u, w maps edges to their weight, and d is a distance map that records the length of the shortest path to each vertex seen so far. p is a predecessor map which records the parent of each vertex, which will ultimately be the parent in the shortest paths tree
RELAX(u, v, w, d, p) if (w(u,v) + d[u] < d[v]) d[v] := w(u,v) + d[u] p[v] := u else ... |
relax edge (u,v) edge (u,v) is not relaxed |
The algorithm repeats this loop |V| times after which it is guaranteed that the distances to each vertex have been reduced to the minimum possible unless there is a negative cycle in the graph. If there is a negative cycle, then there will be edges in the graph that were not properly minimized. That is, there will be edges (u,v) such that w(u,v) + d[u] < d[v]. The algorithm loops over the edges in the graph one final time to check if all the edges were minimized, returning true if they were and returning false otherwise.
BELLMAN-FORD(G) for each vertex u in V d[u] := infinity p[u] := u end for for i := 1 to |V|-1 for each edge (u,v) in E RELAX(u, v, w, d, p) end for end for for each edge (u,v) in E if (w(u,v) + d[u] < d[v]) return (false, , ) else ... end for return (true, p, d) |
initialize vertex u examine edge (u,v) edge (u,v) was not minimized edge (u,v) was minimized |
A directed or undirected graph whose type must be a model of Edge List Graph.IN: Size N
The number of vertices in the graph. The type Size must be an integer type.
The weight (also know as ``length'' or ``cost'') of each edge in the graph. The WeightMap type must be a model of Readable Property Map. The key type for this property map must be the edge descriptor of the graph. The value type for the weight map must be Addable with the distance map's value type.OUT: predecessor_map(PredecessorMap p_map)
Default: get(edge_weight, g)
The predecessor map records the edges in the minimum spanning tree. Upon completion of the algorithm, the edges (p[u],u) for all u in V are in the minimum spanning tree. If p[u] = u then u is either the source vertex or a vertex that is not reachable from the source. The PredecessorMap type must be a Read/Write Property Map which key and vertex types the same as the vertex descriptor type of the graph.IN/OUT: distance_map(DistanceMap d)
Default: dummy_property_map
The shortest path weight from the source vertex to each vertex in the graph g is recorded in this property map. The type DistanceMap must be a model of Read/Write Property Map. The key type of the property map must be the vertex descriptor type of the graph, and the value type of the distance map must be Less Than Comparable.IN: visitor(BellmanFordVisitor v)
Default: get(vertex_distance, g)
The visitor object, whose type must be a model of Bellman-Ford Visitor. The visitor object is passed by value [1].IN: distance_combine(BinaryFunction combine)
Default: bellman_visitor<null_visitor>
This function object replaces the role of addition in the relaxation step. The first argument type must match the distance map's value type and the second argument type must match the weight map's value type. The result type must be the same as the distance map's value type.IN: distance_compare(BinaryPredicate compare)
Default:std::plus<D> with D=typename property_traits<DistanceMap>::value_type.
This function object replaces the role of the less-than operator that compares distances in the relaxation step. The argument types must match the distance map's value type.
Default: std::less<D> with D=typename property_traits<DistanceMap>::value_type.
The time complexity is O(V E).
An example of using the Bellman-Ford algorithm is in examples/bellman-example.cpp.
[1]
Since the visitor parameter is passed by value, if your visitor
contains state then any changes to the state during the algorithm
will be made to a copy of the visitor object, not the visitor object
passed in. Therefore you may want the visitor to hold this state by
pointer or reference.
Copyright © 2000 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu) |