The Only SSSP Algorithm

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: