▶ Bellman-Ford Algorithm

Start — cheapest trips when some legs pay you back. Imagine booking flights between cities where most legs cost money, but a few hand you a coupon or cashback — a “negative” price. You want the cheapest total fare from your home city to every other city. The patient way is to go round after round: at each pass, look at every route and ask “could I get here more cheaply by going through somewhere I already know a good price for?” If yes, write down the cheaper price. Repeat enough passes and the bargains ripple outward until nothing improves. That stubborn, brute-force sweep — not a clever shortcut — is Bellman–Ford, and it is exactly what lets it cope with those money-back legs that trip up greedier methods.

Build — named quantities and the one repeated move. A graph is cities (vertices, $V$) joined by flights (edges, $E$); each edge carries a weight $w(u,v)$, its price — and here it is allowed to be negative. Keep one number per city, $\text{dist}[v]$, the cheapest total found so far from the source $s$, starting at $\text{dist}[s]=0$ and every other $\text{dist}[v]=\infty$. The single move is relaxation: for an edge $u\!\to\!v$, if $\text{dist}[u]+w(u,v)<\text{dist}[v]$, lower $\text{dist}[v]$ to that sum. Worked example: edges $A\!\to\!B=4$, $A\!\to\!C=2$, $C\!\to\!B=-3$. From $A$ a first pass sets $\text{dist}[B]=4$ and $\text{dist}[C]=2$; then relaxing $C\!\to\!B$ gives $2+(-3)=-1<4$, so the true cheapest $A\!\to\!B$ is $-1$, sneaking through $C$. Dijkstra would have locked $B$ at $4$ and missed it.

Deepen — why $V\!-\!1$ rounds, and catching the impossible. A shortest path that never repeats a city visits at most $V$ cities, so it crosses at most $V-1$ edges. Sweep all edges once and every one-edge bargain is found; sweep again and every two-edge bargain locks in; after $V-1$ full sweeps every simple shortest path is settled — a clean induction, and it is really dynamic programming where $\text{dist}$ after round $i$ holds the best cost using at most $i$ edges. That costs $V-1$ rounds $\times\,E$ edges $=O(VE)$, slower than Dijkstra’s $O((V+E)\log V)$, the price of allowing negatives. One more idea earns its keep: run a $V$th sweep — if anything still improves, a path is shrinking by looping, so a negative cycle exists and shortest paths are undefined. Flip every weight to $w=-\log(\text{rate})$ and that same check spots profitable currency arbitrage.

Try this in the panel above. The animated panel is a generic step-through demo of an algorithm trace, so use it to feel the “sweep every edge, lower what you can, repeat” rhythm. Press ▶│ (Next) to advance one operation and ◀ (Back) to retrace it, watching a value drop only when a cheaper route appears. Hit ▶ Play and drop the speed to 0.25× so no pass blurs by. Then drag the n slider to a new size and press ↻ Reset to launch a fresh trace from the top.

Step 1 -- Relaxation Rounds. A shortest path in a graph with V vertices has at most V-1 edges (no repeated vertices in shortest path). Each round relaxes all edges once. After round i, all shortest paths using at most i edges are correctly computed.

Step 2 -- Correctness by Induction. After round 1: all shortest paths of length 1 (direct edges) are correct. After round i: all shortest paths using at most i edges are correct. After V-1 rounds: all shortest paths are correct (since they use at most V-1 edges).

Step 3 -- Time Complexity. V-1 rounds, each relaxing E edges: O(VE). Space: O(V) for dist[] and parent[]. Much slower than Dijkstra O((V+E) log V) for non-negative graphs, but handles negative weights.

Step 4 -- Negative Cycle Detection. After V-1 rounds, if any edge (u,v,w) can still be relaxed (dist[u]+w < dist[v]): a negative cycle exists reachable from source. A negative cycle makes shortest paths undefined (can keep going around to decrease distance infinitely).

Step 5 -- Optimization: Early Termination. If a round passes with no relaxations: already converged, terminate early. Best case O(E) for already-computed or nearly-optimal distances.

Step 6 -- Applications. Currency arbitrage detection (negative cycle = profitable cycle). Network routing with link costs that can be negative. Predecessor to Floyd-Warshall (all-pairs). SPFA (Shortest Path Faster Algorithm) is a queue-optimized Bellman-Ford with O(kE) average where k is small in practice.