31251 Lec 10.3: The Bellman-Ford Algorithm

In this segment we go over the Bellman-Ford algorithm for solving the single-source shortest path problem in a graph where no negative-weight cycle is reachable from the source vertex. The Bellman-Ford algorithm is beautifully simple: when the graph has n vertices, we repeat a loop n-1 times where in the loop we relax every edge in the graph. We show why this algorithm works, and also show how it can be modified to detect the presence of a negative weight cycle.