Bellman-Ford Shortest Path
Hard+115 XPFind shortest paths even with NEGATIVE roads by relaxing every edge V-1 times.
No visualization loaded.
Watch
—
Press Run to begin.
Like Dijkstra, Bellman-Ford finds the cheapest route from a start town to every other town on a weighted map. But it can handle something Dijkstra can't: a road with a NEGATIVE cost (think a road that pays YOU to take it). It keeps a table dist[] of the best-known cost to each town, all starting at ∞ except the start at 0. Then it does one simple thing over and over: 'relax' every road. Relaxing a road from u to v just means checking 'is going to v through u cheaper than what I already know? If yes, write down the cheaper number.' Do that sweep over ALL roads V-1 times (V = number of towns) and every distance settles to the truth.
▸What does it mean to 'relax' an edge?
Relaxing road u→v asks one question: 'Is dist[u] + weight(u,v) smaller than my current dist[v]?' If yes, you've found a cheaper way to reach v, so you lower dist[v] to that new number and remember u as the way you got there. 'Relax' just means 'try to loosen / improve' the current best guess — each relaxation nudges a distance closer to the real answer. Bellman-Ford does this for every road, again and again.
▸Why does Dijkstra break on negative edges but Bellman-Ford doesn't?
Dijkstra's trick is to FINALIZE the closest unvisited town and never look at it again — that's safe only if no future road can ever lower an already-settled cost. A negative road breaks that promise: a town you 'finished' might get cheaper later through a paying road, but Dijkstra has already moved on. Bellman-Ford never finalizes anything early — it just keeps relaxing every edge until nothing improves, so a late negative shortcut still gets caught.
▸Why exactly V-1 rounds?
A shortest path can't repeat a town (repeating would only add cost, assuming no negative cycle), so it visits at most V towns — meaning at most V-1 roads. Each full sweep of all edges lets every shortest path grow by one more road. So after V-1 sweeps, even the longest possible shortest path (V-1 edges) has been fully discovered. More sweeps would change nothing.
▸How does it detect a negative cycle?
After the V-1 rounds, every distance should be final. So Bellman-Ford does ONE more sweep: if any edge can STILL be relaxed (still improves a distance), something is wrong — the only way a distance keeps dropping is a loop of roads whose total cost is negative (a 'negative cycle'). Going around it again and again makes paths cheaper forever, so 'shortest path' has no answer. That extra sweep is the cheap, clever cycle detector.
▸Is Bellman-Ford slower than Dijkstra?
Yes. It relaxes all E edges across V-1 rounds, so it's about O(V·E) — slower than Dijkstra's O((V+E) log V). You pay that extra cost for the power to handle negative weights and to spot negative cycles. Use Dijkstra when all weights are non-negative; reach for Bellman-Ford only when a road can be negative.
How the work grows
O(V·E) is slow — explodes on big inputs. Every round walks all E edges, and there are V-1 rounds, so the work is V·E — roughly a square of the graph size, far heavier than Dijkstra's near-linear cost. You buy the ability to handle negative weights and detect negative cycles. Memory is just the distance table, one number per town.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.