vizlearn
Home / Algorithms

Bellman-Ford and Negative Weights

Algorithms & Data StructuresBy Updated

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-Ford O(V·E)
Dijkstra O(E log V)
Negative edges supported

Overview

Bellman–Ford computes shortest paths from one source even when edges have negative weights. It repeatedly relaxes every edge, then checks once more for a reachable negative cycle, which means no finite shortest path exists for affected vertices.

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. Exactly the update Dijkstra would have missed.

Relax every edge 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) — much slower than Dijkstra's O(E log V).

Detecting negative cycles

This is Bellman-Ford's distinctive capability, and the reason it is still used despite being slower.

If a cycle's total weight is negative, going round it again always reduces the distance. There is no shortest path — the answer is negative infinity.

The detection is elegant: after V−1 rounds every genuine shortest path has been found. So if one more round still improves something, a negative cycle must be reachable. That is the final loop in the code above.

To find the cycle itself rather than merely detect it: record a parent for each vertex. And when the extra round relaxes an edge, walk the parent chain backwards V times to land inside the cycle. Then trace round it.

Note the phrase "reachable from source". A negative cycle in a disconnected part of the graph does not affect the answer and will not be detected from that source.

Why Dijkstra cannot do this: it finalises each vertex once, on the assumption that no later path can be shorter. A negative edge breaks that assumption silently, so Dijkstra returns a wrong answer rather than an error — which is worse than failing.

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.

Why V−1 rounds

A shortest path in a graph with V vertices contains at most V−1 edges. Any more would repeat a vertex, and repeating a vertex means a cycle. This cannot help unless it is negative.

Each round of relaxation guarantees that all shortest paths using one more edge than before are correct. So after round 1 all one-edge shortest paths are settled. After round 2 all two-edge paths, and after V−1 rounds every possible shortest path is found.

That gives O(V × E), which is much worse than Dijkstra's O((V+E) log V). The changed flag helps in practice — most graphs converge well before V−1 rounds — and the worst case stands.

AlgorithmWeightsComplexityDetects negative cycles
BFSUnweightedO(V+E)N/A
DijkstraNon-negativeO((V+E) log V)No
Bellman-FordAnyO(VE)Yes
Floyd-WarshallAny, all pairsO(V³)Yes
JohnsonAny, all pairs, sparseO(V² log V + VE)Yes

Things to try with Bellman-Ford and Negative Weights

  1. Run the negative-edge graph. Watch a distance get improved in a later pass. The exact case Dijkstra gets wrong.
  2. Count the passes. V−1 of them, each relaxing every single edge whether or not it helps.

Sources and next steps

Run it in Python

V − 1 rounds of relaxing every edge, with the distance table printed after each round so you can watch it settle — and then one extra round, which is the entire negative-cycle detector.

bellman_ford.pyPython 3
Output
How the code works
  1. for round_no in range(1, len(nodes)):V − 1 rounds, and not one more. A shortest path visits each node at most once, so it has at most V − 1 edges — and each round is guaranteed to settle at least one more edge of it.
  2. if dist[u] != float("inf") and dist[u] + w < dist[v]:The infinity guard matters: inf + -5 is still inf in floating point, but relaxing from a node you have not reached yet is meaningless and pollutes the parent map.
  3. for u, v, w in edges:Every edge, every round, in whatever order the list happens to be in. That brute force is the reason negative weights are safe here where they break Dijkstra.
  4. if not changed: breakA round that changes nothing means every later round changes nothing either. Typical graphs settle long before V − 1 rounds, so this is most of the practical speed.
  5. one more pass -> return TrueAfter V − 1 rounds the distances are final if they exist. An edge that still improves therefore proves a cycle whose total weight is negative — there is no shortest path at all, because going round once more is always cheaper.
Change one thing
  • Reverse edges before running. The intermediate rounds differ — edge order changes how fast it converges, never the answer.
  • Print the round number the early exit fires on. On this graph it is well short of V − 1; construct a path graph A→B→C→... with the edges listed backwards to force the full count.
  • Delete the early exit and the final pass, then run the negative-cycle version. The distances just keep falling — that is what the detector is protecting you from.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: switch Graph to Negative cycle. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. Why exactly V - 1 rounds?
  2. How does the algorithm detect a negative cycle?
  3. Compared with Dijkstra, Bellman-Ford is:





 Cheat sheet
Bellman-Ford and Negative Weights
Relax every edge V-1 times to find shortest paths with negative weights, then run one extra pass to detect negative cycles.
ALGORITHMS · vizlearn.in/dsa/bellman_ford.html
More in Algorithms
AlgorithmsA* Pathfinding AlgorithmAlgorithmsMinimum Spanning TreeAlgorithmsTwo PointersAlgorithmsSliding Window
Further reading
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact