Single Source Shortest Paths (SSSP)

We want to find the shortest distance from starting vertex s to all other vertices in G. The final output is an array dist[z], the distance from s to z.

Bellman Ford

If there are no negative cycles, the shortest path \cal P exists and |\cal P| \leq n-1 edges.

DP Recurrence

Label each edge from i = 0\dots n-1.

For i = 0\dots n-1 and z\in V, the subproblem is: D(i, z) = the length of the shortest path from s to z using \leq i edges.

The base cases is when we use 0 edges:

\begin{aligned}
D(0, s) &= 0\\
D(0, z) &= \infty \,\forall z\neq s    
\end{aligned}

In the recursive case, consider:

The second-to-last vertex y where yz\in E. Try each possible choice of y i.e. every vertex that has z as its neighbor:
```
 \min_{y:yz\in E}\{D(i-1, y) + w(yz)\}
```
where w(yz) is the weight.
Don't use y, see if we can reach z with i-1 edges
```
 D(i-1, z)
```

Finally take the min of both:

D(i, z) = \min\left\{\begin{aligned}
    &\min_{y:yz\in E}\{D(i-1, y) + w(yz)\}\\ 
    &D(i-1, z)
\end{aligned}\right\}

Find Negative weight cycles

Check if D(|V|, z) < D(|V| - 1, z) for some z\in V. If so, then we have a negative cycle. The z that's not a sink is where the negative cycle happens.

If not, then we can use either D(|V|, *) or D(|V|-1, *) as the final return array.

Note that Bellman-Ford can only find negative cycles that are REACHABLE from s.