Medium Problemsgraphminimization
Bellman–Ford Algorithm
Find the shortest distance from one source vertex to every other vertex in a weighted directed graph that may contain negative edge weights, and report whether a negative cycle exists.
Note. Filed under Medium in the course's source list. It is a graph relaxation algorithm rather than textbook tabulation, though its layer-by-layer relaxation is genuinely a DP over 'shortest path using at most k edges'.
Do this lesson first: coin changeThe full breakdown and animated table for this problem are still being written. In the meantime, run the four questions on it yourself — that is the whole exercise.