Bellman Ford Algorithm

Basic Theorem

Theorem 1: In a graph with no negative-weight cycles with N vertices, the shortest path between any two vertices has at most \(n - 1\) edges.

Negative-weight cycle: sum of weights in the cycle < 0.

Theorem 2: In a graph with negative-weight cycles, there is no shortest path.

Algorithm