Bellman-Ford Algorithm for SSSP
Let G be a directed graph, s a node of G,
and cost a cost function on the edges of G.
Edge costs may be positive or negative. A single source shortest path
algorithm computes the shortest paths from s to all other
nodes of G with respect to cost.
Remark: Finding the shortest path from one node to one other
node is not significantly faster than computing the shortest paths from
the source to all other nodes.
BELLMAN_FORD_T() is the LEDA function for computing
single source shortest paths in a directed graph. BELLMAN_FORD_T()
is a template function. The template parameter NT can be
instantiated with any number type.
Example of How
to Use BELLMAN_FORD_T()
BELLMAN_FORD() is the name of the preinstantiated
version of BELLMAN_FORD_T(). There is one function BELLMAN_FORD()
for edge costs of type int and one for double.
Example of How to
Use BELLMAN_FORD()
Important Notice: BELLMAN_FORD() only performs correctly
if all arithmetic is performed without rounding errors and without overflows.
If you are not sure about this, you should use BELLMAN_FORD_T()
with one of the LEDA number types.
Running time
The running time of BELLMAN_FORD_T() and BELLMAN_FORD()
for a graph G=(V,E) is O(|V||E|).
Tips
|