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

• If your graph contains cycles and there are edges with negative costs, use BELLMAN_FORD_T().
• If you know that there can be no overflows and no rounding errors you can use BELLMAN_FORD().
• The Generic Algorithms for SSSP provide a convenient interface to all SSSP algorithms in LEDA. You do not have to think about cycles and negative edge costs beforehand.
• If your graph is acyclic, you can also use SSSP Algorithm for Acyclic Graphs.
• If your edge costs are non-negative, you can use Dijkstra's Algorithm for SSSP.
• LEDA also provides functions for checking the results of an SSSP Algorithm.

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