Bellman-Ford algorithm
Find shortest paths even when some edges have negative weights, while detecting negative cycles.
Big idea
How it thinks about the graph
Relax every edge repeatedly. After enough passes, all shortest paths without negative cycles must have settled.
Useful when
Networks with gains, penalties, exchange rates or situations where negative weights are meaningful.
Watch out: It is usually slower than Dijkstra's algorithm, but it handles cases Dijkstra cannot.
Questions to investigate
Why does relaxing every edge repeatedly eventually work?
What would a negative cycle mean in a real context?
How can a path keep getting cheaper forever?
Interactive version planned
The page is here now so the topic has a clear place in the site. The next step will be to build a visual step-through version of the algorithm.