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:

$\underline{InitSSSP(s):} \\ \hspace{0.4cm} dist(s) ← 0 \\ \hspace{0.4cm} pred(s) ← Null \\ \hspace{0.4cm} for\space all\space vertices\space v \neq s \\ \hspace{1cm} dist(v) ← ∞ \\ \hspace{1cm} pred(v) ← Null$ ...