# The Only SSSP Algorithm

Get to know the only algorithm used to solve the single-source shortest paths problem in general graphs.

## Lester Ford algorithm for SSSP

Just like graph traversal and minimum spanning trees, many different SSSP algorithms can be described as special cases of a single generic algorithm, first proposed by Lester Ford in 1956 and independently described by George Dantzig in 1957 and again by George Minty in 1958. Each vertex $v$ in the graph stores two values, which (inductively) describe a tentative shortest path from $s$ to $v$.

- $dist(v)$ is the length of the tentative shortest $s\rightarrow v$ path, or ∞ if there is no such path.
- $pred(v)$ is the predecessor of $v$ in the tentative shortest $s\rightarrow v$ path, or $Null$ if there is no such vertex.

## Initialization and predecessors

The predecessor pointers automatically define a tentative shortest path tree rooted at $s$; these pointers are exactly the same as the parent pointers in our generic graph traversal algorithm. At the beginning of the algorithm, we initialize the distances and predecessors as follows:

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy