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.
The mechanism is relaxation, repeated:
if dist[u] + weight(u,v) < dist[v]: dist[v] = dist[u] + weight(u,v)
Apply that to every edge, V−1 times.
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.
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.