BellmanFord 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(VE).
Tips

See also:
Shortest Path Algorithms
Checking the Results of an SSSP Algorithm
Generic Algorithms for SSSP
SSSP Algorithm for Acyclic Graphs
Dijkstra's Algorithm for SSSP
Number Types
Graphs and Related Data Types
Graph Algorithms
Manual Entries:
Manual
Page Shortest Path Algorithms
