Dijkstra breaks when an edge has negative weight. Bellman-Ford relaxes every edge V−1 times instead of trusting a greedy choice — slower, but it copes, and it can prove a negative cycle exists.
Controls
for i in range(V-1):
for (u,v,w) in edges:
if d[u]+w < d[v]:
d[v] = d[u]+w
# extra pass detects a# negative cycle
Relaxing Every Edge
step 0
Distance from A
Insight
Relaxation is the whole algorithm: if going through u reaches v more cheaply than the current best, update it.
pass0 / –
relaxations0
edges checked0
Complexity
Bellman-FordO(V·E)
DijkstraO(E log V)
Negative edgessupported
Bellman-Ford and Negative Weights
Slower than Dijkstra, but it handles what Dijkstra cannot.
Quick Context
Bellman-Ford finds shortest paths from one source, like Dijkstra — but it works with negative edge weights, and it can detect when no shortest path exists at all.
Why Dijkstra Fails on Negative Edges
Dijkstra is greedy: once it finalises a vertex's distance, it never revisits it. That relies on an assumption — that adding more edges can only make a path longer.
A negative edge breaks it. A vertex finalised early might later be reachable more cheaply via a negative edge, but Dijkstra has already moved on. Load Has a negative edge and watch Bellman-Ford improve a distance in a later pass — precisely the update Dijkstra would have missed.
Relax Everything, V−1 Times
Bellman-Ford makes no greedy commitment. It simply relaxes every edge, repeatedly:
Why V−1 passes? A shortest path can contain at most V−1 edges (any more would revisit a vertex, forming a cycle). Each pass guarantees correctness for paths one edge longer, so V−1 passes settle every possible path.
This brute-force honesty costs O(V·E) — considerably slower than Dijkstra's O(E log V).
Detecting Negative Cycles
If a cycle's edges sum to a negative number, you can loop it forever and drive the distance to negative infinity — no shortest path exists.
Bellman-Ford detects this elegantly. After V−1 passes everything should be final, so it runs one extra pass. If any distance still improves, a negative cycle must exist. Load the third graph and watch that final pass fire.
This is not a curiosity: it is used to detect arbitrage in currency exchange, where taking the log of exchange rates turns a profitable loop into a negative cycle.
When Negative Weights Are Real
They sound artificial until you meet them: financial transactions with gains and losses, chemical reactions with energy release, game scoring with penalties and bonuses, or any cost model where some moves refund you.
Related algorithms worth knowing: Floyd-Warshall computes all-pairs shortest paths in O(V³) and also tolerates negative edges; Johnson's algorithm reweights a graph with Bellman-Ford so Dijkstra can then run on it safely.
Interactive Exploration Guide
Run the negative-edge graph. Watch a distance get improved in a later pass — the exact case Dijkstra gets wrong.
Count the passes. V−1 of them, each relaxing every single edge regardless of whether it helps.
Compare with the all-positive graph. Bellman-Ford still does the full V−1 passes — it cannot stop early the way Dijkstra can.
Load the negative cycle. The extra verification pass still finds an improvement, which proves no shortest path exists.
Note the relaxation counter. Most edge checks change nothing — that redundancy is the price of handling negative weights.
Key Takeaway
Bellman-Ford relaxes every edge V−1 times instead of committing greedily, so it survives negative weights at O(V·E). One extra pass turns it into a negative-cycle detector. Use Dijkstra when all weights are non-negative; reach for this when they are not.
Cheat sheet
Bellman-Ford and Negative Weights
Dijkstra breaks when an edge has negative weight. Bellman-Ford relaxes every edge V−1 times instead of trusting a greedy choice — slower, but it copes, and it can prove a negative cycle exists.