Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Shortest Path Algorithms > Bellman-Ford Algorithm for SSSP

## 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

Shortest Path Algorithms

Checking the Results of an SSSP Algorithm

Generic Algorithms for SSSP

Number Types

Graphs and Related Data Types

Graph Algorithms

Manual Entries: