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.
The idea in brief
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
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 predecessor for each vertex, and when the extra round relaxes an edge, walk the predecessor 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.
Shortest paths when weights can be negative
Dijkstra's algorithm is faster and it assumes every edge weight is non-negative. Bellman-Ford drops that assumption, and it can additionally detect when no shortest path exists at all.
def bellman_ford(n, edges, source):
INF = float("inf")
dist = [INF] * n
dist[source] = 0
for _ in range(n - 1): # V-1 rounds
changed = False
for u, v, w in edges:
if dist[u] != INF and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
changed = True
if not changed:
break # converged early
for u, v, w in edges: # one extra round
if dist[u] != INF and dist[u] + w < dist[v]:
raise ValueError("negative cycle reachable from source")
return dist
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, which 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 considerably 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.
Algorithm
Weights
Complexity
Detects negative cycles
BFS
Unweighted
O(V+E)
N/A
Dijkstra
Non-negative
O((V+E) log V)
No
Bellman-Ford
Any
O(VE)
Yes
Floyd-Warshall
Any, all pairs
O(V³)
Yes
Johnson
Any, all pairs, sparse
O(V² log V + VE)
Yes
V-1 rounds, and why that number is exactly right
Bellman-Ford relaxes every edge V-1 times, which looks like a magic constant until you watch the distances settle. Print the table after each round and you can see information travelling one edge per round -- and see that it stops changing well before the bound in most cases, and exactly at it in the worst.
example_01.pyPython
EDGES = [("A", "B", 4), ("A", "C", 5), ("B", "C", -3),
("C", "D", 4), ("B", "E", 10), ("D", "E", -2)]
NODES = ["A", "B", "C", "D", "E"]
def bellman_ford(edges, nodes, start, verbose=True):
dist = {n: float("inf") for n in nodes}
dist[start] = 0
if verbose:
print("round " + " ".join("%5s" % n for n in nodes))
print("%5d " % 0 + " ".join(
"%5s" % ("inf" if dist[n] == float("inf") else dist[n])
for n in nodes))
for r in range(1, len(nodes)):
changed = False
for u, v, w in edges:
if dist[u] != float("inf") and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
changed = True
if verbose:
print("%5d " % r + " ".join(
"%5s" % ("inf" if dist[n] == float("inf") else dist[n])
for n in nodes) + ("" if changed else " <- nothing changed"))
if not changed:
break
# one extra pass: anything that still improves means a negative cycle
for u, v, w in edges:
if dist[u] != float("inf") and dist[u] + w < dist[v]:
return dist, True
return dist, False
dist, neg = bellman_ford(EDGES, NODES, "A")
print("negative cycle:", neg)
# This graph finished in one round and the second round changed nothing,
# so the loop stopped early. That is the common case: V-1 is a bound, not
# a schedule, and the edges here happened to be listed in an order that
# carried the distances all the way in a single pass.
#
# Note that C ended at 1, via A -> B -> C for 4 + (-3), not at 5 via
# the direct edge. Dijkstra would have settled C at 5 and never revisited
# it. Bellman-Ford has no notion of settled, which is exactly why the
# negative edge does not break it.
#
# Now the case that needs every round. A chain, with the edges listed in
# the worst possible order:
chain_nodes = ["n0", "n1", "n2", "n3", "n4", "n5"]
chain = [("n4", "n5", 1), ("n3", "n4", 1), ("n2", "n3", 1),
("n1", "n2", 1), ("n0", "n1", 1)]
print()
print("a 6-node chain with edges in reverse order:")
bellman_ford(chain, chain_nodes, "n0")
# NOW the propagation is visible: one more column per round, because each
# round lets every distance advance exactly one more edge. Five rounds for
# six nodes -- V-1 exactly, and not one fewer.
#
# That is where the constant comes from. A shortest path in a graph with V
# nodes visits at most V nodes, so it has at most V-1 edges, so V-1 rounds
# is always enough however badly the edges are ordered.
#
# Feed the same edges in forward order and the same graph finishes in one
# round: the bound is about the worst ordering, not about the graph.
print()
print("the same chain with edges in forward order:")
bellman_ford(list(reversed(chain)), chain_nodes, "n0")
# And the thing Dijkstra cannot do at all: report that the question has
# no answer.
CYCLE = [("A", "B", 1), ("B", "C", -3), ("C", "A", 1)]
dist, neg = bellman_ford(CYCLE, ["A", "B", "C"], "A", verbose=False)
print()
print("graph with a negative cycle -- detected:", neg)
# Going round that loop costs 1 - 3 + 1 = -1, so a path can be made
# arbitrarily cheap by going round again. There is no shortest path, and
# the extra pass is what turns that into a reported fact rather than a
# wrong number.
Output
Things to try
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.
In one line
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.
Where negative weights actually occur
Negative weights sound artificial, and they arise naturally in several domains.
Currency arbitrage. Take the negative logarithm of each exchange rate as the edge weight. A negative cycle then means a sequence of trades returning more currency than it started with — a risk-free profit. Detecting it is exactly Bellman-Ford's negative-cycle check, and this is a real application in financial systems.
Net cost with rebates. A route that earns a subsidy, a process step that recovers energy, a transaction with a refund — all give edges with negative net cost.
Difference constraints. Systems of inequalities of the form xᵢ − xᵚ ≤ c are solved by building a graph with edge weights c and running Bellman-Ford. Infeasibility appears as a negative cycle. This is used in scheduling and in compiler optimisation.
Reduced costs in linear programming and network flow algorithms, where potentials produce negative-weight residual edges.
So the algorithm's role is: the one to reach for when weights might be negative, and the one that tells you when the question has no answer.
SPFA, the practical optimisation
The Shortest Path Faster Algorithm is Bellman-Ford with a queue: only relax edges leaving vertices whose distance actually changed, rather than sweeping every edge every round.
from collections import deque
def spfa(n, graph, source):
INF = float("inf")
dist = [INF] * n
dist[source] = 0
in_queue = [False] * n
count = [0] * n # relaxations per vertex
q = deque([source]); in_queue[source] = True
while q:
u = q.popleft(); in_queue[u] = False
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
if not in_queue[v]:
q.append(v); in_queue[v] = True
count[v] += 1
if count[v] >= n:
raise ValueError("negative cycle")
return dist
On typical graphs this is dramatically faster than the naive sweep — often close to O(E). Its worst case remains O(VE), and adversarial inputs exist that trigger it, so it is a practical optimisation rather than a complexity improvement.
The counter provides negative-cycle detection: a vertex entering the queue V or more times means it is being improved indefinitely.
Distributed routing, and the count-to-infinity problem
Bellman-Ford is naturally distributed: each node needs only its neighbours' distance estimates, not global knowledge. That is why it underlies distance-vector routing protocols such as RIP, where routers exchange distance tables with neighbours.
It also has a famous failure mode there. When a link goes down, routers can slowly increment each other's estimates — A thinks it can reach the destination via B, B thinks via A — converging towards infinity one step at a time. That is the count-to-infinity problem, and the mitigations (split horizon, poison reverse, a maximum hop count of 16 in RIP) are all workarounds for it.
Link-state protocols such as OSPF avoid it by having every router build a complete map and run Dijkstra locally. That is the practical trade: Bellman-Ford needs no global view and converges slowly; Dijkstra needs the whole topology and converges immediately.
Questions people ask
When should I use Bellman-Ford over Dijkstra? Only when weights can be negative, or when you need negative-cycle detection. Otherwise Dijkstra is much faster.
What happens if I use Dijkstra with negative weights? It returns a wrong answer without any error, because it finalises vertices too early.
Why exactly V−1 rounds? A shortest path uses at most V−1 edges, and each round settles paths one edge longer.
How do I find the negative cycle, not just detect it? Track predecessors; from a vertex relaxed in the extra round, walk back V times to land in the cycle, then trace it.
Is SPFA always faster? Usually, and not in the worst case — adversarial graphs still force O(VE).
What about all-pairs shortest paths with negative edges? Floyd-Warshall for dense graphs, or Johnson's algorithm (Bellman-Ford once, then Dijkstra from each vertex) for sparse ones.
Recap in one screen
Relax every edge V−1 times; each round settles shortest paths one edge longer.
It handles negative weights, which Dijkstra cannot — and Dijkstra fails silently rather than erroring.
One extra round that still improves something proves a reachable negative cycle exists.
O(VE), which is slow; SPFA's queue makes it fast in practice without improving the worst case.
It is the basis of distance-vector routing, along with the count-to-infinity problem that follows.
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
# Bellman-Ford: relax EVERY edge, V-1 times. Slower than Dijkstra,
# but it copes with negative weights and can prove a negative cycle exists.
edges = [("A", "B", 4), ("A", "C", 5), ("B", "C", -3),
("B", "D", 2), ("C", "E", 4), ("D", "E", -1), ("E", "F", 2)]
nodes = ["A", "B", "C", "D", "E", "F"]
def bellman_ford(nodes, edges, start):
dist = {n: float("inf") for n in nodes}
dist[start] = 0
parent = {start: None}
for round_no in range(1, len(nodes)): # V - 1 rounds
changed = False
for u, v, w in edges:
if dist[u] != float("inf") and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
parent[v] = u
changed = True
shown = {n: (d if d != float("inf") else "inf") for n, d in dist.items()}
print(f"round {round_no}: {shown}")
if not changed: # nothing moved; it is settled
print(" no change - stopping early")
break
# One more pass. Any further improvement means a negative cycle.
for u, v, w in edges:
if dist[u] != float("inf") and dist[u] + w < dist[v]:
return dist, parent, True
return dist, parent, False
dist, parent, negative = bellman_ford(nodes, edges, "A")
print()
print("distances :", dist)
print("negative cycle? :", negative)
print()
print("Adding an edge E -> B of -5, which closes a negative loop:")
edges.append(("E", "B", -5))
dist, parent, negative = bellman_ford(nodes, edges, "A")
print("negative cycle? :", negative)
print("B -> D -> E -> B costs 2 + -1 + -5 = -4, so going round again is free money.")
Output
How the code works
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.
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.
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.
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.
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.
Check yourself
0 of 3
Answer without scrolling back up.
Why exactly V - 1 rounds?
Each round settles at least one more edge of any shortest path, so V - 1 rounds is enough and one more would be wasted.
How does the algorithm detect a negative cycle?
After V - 1 rounds the distances are final if they exist. A further improvement proves you can keep going round and getting cheaper, so no shortest path exists.
Compared with Dijkstra, Bellman-Ford is:
O(V·E) against O(E log V). You pay for the generality, which is why Dijkstra remains the default when weights are non-negative.
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.
On a Routing ProblemBellman, Quarterly of Applied Mathematics 1958
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.