Intuition First: Roads That Pay You Back#
Dijkstra's GPS assumed every road costs you something. But some edges can pay you back. Think of converting currencies: trading dollars → euros → yen → dollars might leave you with more money than you started, because some exchange "edges" are effectively negative. Dijkstra's "lock it in and never look back" trick breaks here: a bargain discovered later really can beat one you already committed to.
Bellman-Ford fixes this with brute honesty: instead of being clever about order, it just relaxes every road, over and over, letting better deals ripple through the graph. And if doing one more pass still keeps finding cheaper paths, it has caught a money-printing loop (a negative cycle) and says so.