Motivation
Lesson 2 of 9 in Coddy's Bellman-Ford Algorithm - Graph Algorithms course.
Bellman-Ford is built on one operation, relaxation: for an edge u -> v of weight w, if going through u is cheaper (dist[u] + w < dist[v]), update dist[v]. Do that for every edge, repeatedly.
Why learn Bellman-Ford?
- Negative weights: it works where Dijkstra cannot, for example costs that can be rebates or currency arbitrage.
- Negative-cycle detection: one extra relaxation pass reveals cycles whose total weight is negative.
- Simplicity: no priority queue, just repeated edge relaxation.
The trade-off is speed: O(V * E), slower than Dijkstra's O((V + E) log V).
Try it yourself
This lesson doesn't include a code challenge.
Test yourselfThis lesson includes a short quiz. Start the lesson to answer it and track your progress.
