Bellman-Ford Algorithm for SSSP
G be a directed graph,
s a node of
cost a cost function on the edges of
Edge costs may be positive or negative. A single source shortest path
algorithm computes the shortest paths from
s to all other
G with respect to
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.
is a template function. The template parameter
NT can be
instantiated with any number type.
Example of How
BELLMAN_FORD() is the name of the preinstantiated
BELLMAN_FORD_T(). There is one function
for edge costs of type
int and one for
Example of How to
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
with one of the LEDA number types.
The running time of
for a graph
G=(V,E) is O(|V||E|).
Shortest Path Algorithms
Checking the Results of an SSSP Algorithm
Generic Algorithms for SSSP
SSSP Algorithm for Acyclic Graphs
Dijkstra's Algorithm for SSSP
Graphs and Related Data Types
Page Shortest Path Algorithms