Bellman-Ford

Shortest paths with NEGATIVE edge weights — the case Dijkstra can't handle. Relax every edge, V−1 times.

Why Dijkstra breaks

• Dijkstra settles a node the first time it's popped — freezes its distance
• A negative edge can reveal a cheaper route later → too late, already settled
• Bellman-Ford never settles: relax ALL edges, pass after pass
• After pass k: every distance reachable in ≤ k edges is final

Watch distances ripple

Numbers = distance estimates · red edge = negative (2→1, w=−3). Node 1 drops 4 → 2 via the negative edge; pass 2 propagates it onward.

What you're buying

30% negative edges → Dijkstra silently wrong on ~5% of nodes. Bellman-Ford: always right.

Cycle detection for free

• V−1 passes settle everything (shortest simple path ≤ V−1 edges)
• A V-th pass that still relaxes ⇒ a reachable NEGATIVE CYCLE
• Then no shortest path exists — report the cycle (that's arbitrage detection)
• O(V·E): the price of not being clever about order

Takeaway

Dijkstra faster but only valid on non-negative graphs — it lies, it doesn't crash. Bellman-Ford = dynamic programming on graphs, the truthful fallback. Next: all-pairs at once → Floyd-Warshall.