The Only SSSP Algorithm

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

We'll cover the following

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: