Bellman-Ford Overview and Motivation
What You'll Learn
You'll discover why we need an alternative to Dijkstra's algorithm when graphs contain negative edge weights.
Why Bellman-Ford Exists
Remember from lesson 971 that Dijkstra's algorithm breaks down when edges have negative weights? This is where the Bellman-Ford algorithm comes to the rescue.
Imagine you're calculating the cheapest route between cities, but some roads offer cashback rewards (represented as negative weights). Dijkstra's greedy approach fails here because it assumes once you've found the shortest path to a node, you're done—but a negative edge discovered later could actually make an earlier path cheaper.
The Core Idea
Bellman-Ford takes a more cautious, exhaustive approach. Instead of greedily selecting the "closest" unvisited node, it:
- Relaxes every edge in the graph (tries to improve the shortest path estimate)
- Repeats this process multiple times (specifically, V-1 times for V vertices)
By systematically checking all edges repeatedly, Bellman-Ford ensures that even negative weights are properly accounted for. Think of it as "spreading" distance information across the graph in waves, with each iteration potentially discovering cheaper paths.
The Bonus Feature
Unlike Dijkstra's, Bellman-Ford can also detect negative cycles—loops where the total weight is negative. These are problematic because you could keep looping forever, making distances infinitely small. Bellman-Ford identifies these situations, which is crucial for applications like currency arbitrage detection.
Key Takeaway: Bellman-Ford sacrifices Dijkstra's speed for the ability to handle negative edge weights and detect negative cycles, making it essential when your graph contains "discounts" or similar negative-cost scenarios.