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 vv in the graph stores two values, which (inductively) describe a tentative shortest path from ss to vv.

  • dist(v)dist(v) is the length of the tentative shortest svs\rightarrow v path, or ∞ if there is no such path.
  • pred(v)pred(v) is the predecessor of vv in the tentative shortest svs\rightarrow v path, or NullNull if there is no such vertex.

Initialization and predecessors

The predecessor pointers automatically define a tentative shortest path tree rooted at ss; 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