Bellman-Ford and Negative Cycles
Run n-1 relaxation passes over all edges, detect negative cycles with a final pass, and explain why Dijkstra fails on negative-weight edges.
Bellman-Ford and Negative Cycles is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Why Bellman-Ford Exists
Bellman-Ford solves the single-source shortest path problem like Dijkstra, but it handles negative edge weights. It also detects negative cycles — cycles whose total weight is negative, making it impossible to define a finite shortest path through them. While slower than Dijkstra, Bellman-Ford is the correct choice whenever the graph may contain negative-weight edges.
Relaxation: The Core Operation
Bellman-Ford is built on a single operation: relaxation. Relaxing edge (u, v, w) means: if dist[u] + w < dist[v], update dist[v] = dist[u] + w. We repeatedly relax all edges. The key insight is: any shortest path has at most V-1 edges (in a graph with no negative cycles). Therefore, V-1 rounds of relaxation over all edges are sufficient to find all shortest paths.
Bellman-Ford Implementation
Represent the graph as an edge list [(u, v, weight)]. Initialise dist[source] = 0 and all others to inf. Run V-1 rounds, relaxing all edges each round. Any update that still occurs in a Vth round indicates a negative cycle.
def bellman_ford(V, edges, source):
dist = [float('inf')] * V
dist[source] = 0
# V-1 relaxation passes
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# V-th pass: detect negative cycle
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return None # negative cycle exists
return dist
edges = [(0,1,4),(0,2,5),(1,2,-3),(2,3,1)]
print(bellman_ford(4, edges, 0)) # [0, 4, 1, 2]Why V-1 Passes Are Sufficient
A shortest path in a graph without negative cycles visits each node at most once, so it has at most V-1 edges. After round 1, the shortest 1-hop paths are optimal. After round 2, the shortest 2-hop paths are optimal. After V-1 rounds, all shortest paths (which use at most V-1 hops) have been found. If round V still updates a distance, the graph contains a negative cycle reachable from the source.
Negative Cycle Detection
After V-1 passes, run one additional pass over all edges. If any edge (u, v, w) satisfies dist[u] + w < dist[v], then a negative cycle exists and the shortest path to some nodes is -infinity. Real-world applications include detecting arbitrage opportunities in currency exchange (negative cycles in log-weight graphs) and detecting inconsistencies in constraint systems.
def has_negative_cycle(V, edges, source):
dist = [float('inf')] * V
dist[source] = 0
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Nth pass
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return True # negative cycle detected
return False
# Negative cycle: 1->2->3->1 with weights -1,-1,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-1),(2,3,-1),(3,1,1)]
print(has_negative_cycle(4, edges_neg, 0)) # TrueComparing Dijkstra and Bellman-Ford
Dijkstra: O((V+E) log V), requires non-negative weights, greedy approach. Bellman-Ford: O(V × E), handles negative weights, detects negative cycles. For most interview problems with non-negative weights, Dijkstra is preferred. When negative weights appear (e.g., 'find shortest path with negative cost edges' or 'detect arbitrage'), Bellman-Ford is the answer. For dense graphs, Bellman-Ford's O(V³) worst case is comparable to Floyd-Warshall.
Application: Cheapest Flights with Bellman-Ford
Cheapest Flights Within K Stops (LeetCode 787) can be solved with a modified Bellman-Ford: run exactly k+1 relaxation passes (since k stops means k+1 edges). Use a copy of the distances from the previous pass to ensure we don't use more hops than allowed in a single pass — otherwise a single pass could chain multiple hops.
def findCheapestPrice_bf(n, flights, src, dst, k):
dist = [float('inf')] * n
dist[src] = 0
for _ in range(k + 1): # k stops = k+1 edges
temp = dist[:] # copy to avoid using updated dist in same pass
for u, v, w in flights:
if dist[u] != float('inf') and dist[u] + w < temp[v]:
temp[v] = dist[u] + w
dist = temp
return dist[dst] if dist[dst] != float('inf') else -1
print(findCheapestPrice_bf(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1)) # 200SPFA: Queue-Based Optimisation
Shortest Path Faster Algorithm (SPFA) is an optimised Bellman-Ford that only re-relaxes edges from nodes whose distance was just updated, using a queue. Average case is O(E) but worst case remains O(V × E). SPFA is rarely required in interviews, but you may mention it as an optimisation when Bellman-Ford is too slow on sparse graphs. Python does not have a built-in SPFA, but it's straightforward to implement with collections.deque.
Currency Arbitrage Detection
A classic Bellman-Ford application: given currency exchange rates, detect if arbitrage is possible (a cycle where converting currencies returns more than you started with). Transform by taking negative logarithm of exchange rates. Arbitrage = a cycle with negative total log-weight = negative cycle detectable by Bellman-Ford. This maps real-world financial problems to the standard algorithm.
import math
def has_arbitrage(rates):
n = len(rates)
# Transform: -log(rate) converts product to sum
log_rates = [[-math.log(rates[i][j]) for j in range(n)] for i in range(n)]
edges = [(i,j,log_rates[i][j]) for i in range(n) for j in range(n) if i != j]
dist = [float('inf')] * n
dist[0] = 0
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in edges:
if dist[u] + w < dist[v]:
return True # arbitrage!
return FalseEarly Termination Optimisation
If no distance is updated in a full pass over all edges, subsequent passes won't update anything either — terminate early. This optimisation reduces best-case complexity to O(E) when the graph is already optimal after few passes. Add a flag updated = False at the start of each pass; if it remains False after the pass, break immediately.
def bellman_ford_optimised(V, edges, source):
dist = [float('inf')] * V
dist[source] = 0
for _ in range(V - 1):
updated = False
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
updated = True
if not updated:
break # no more improvements possible
return distBellman-Ford on Graphs with Adjacency Lists
When the graph is given as an adjacency list rather than an edge list, convert to an edge list first or iterate over all adjacency list entries as edges. For V=1000 and E=5000, V-1=999 passes each scanning 5000 edges gives 4,995,000 operations — well within time limits. For very dense graphs (E ≈ V²), the O(V³) worst case matches Floyd-Warshall, making the choice context-dependent.
from collections import defaultdict
def bellman_ford_adj(V, adj, source):
# Convert adjacency list to edge list
edges = [(u, v, w) for u in range(V) for v, w in adj[u]]
dist = [float('inf')] * V
dist[source] = 0
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
return distQuick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: Bellman-Ford relaxes all edges V-1 times to handle negative-weight edges, a Vth relaxation pass that still finds improvements indicates a negative cycle, and the algorithm is O(V × E) compared to Dijkstra's O((V+E) log V). Next up we cover Floyd-Warshall for all-pairs shortest paths in a single O(V³) computation.
Frequently asked questions
Is the “Bellman-Ford and Negative Cycles” lesson free?
Yes — the full text of “Bellman-Ford and Negative Cycles” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Bellman-Ford and Negative Cycles”?
Run n-1 relaxation passes over all edges, detect negative cycles with a final pass, and explain why Dijkstra fails on negative-weight edges. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Bellman-Ford and Negative Cycles” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Dijkstra's Algorithm with a Priority Queue
- Bellman-Ford and Negative Cycles
- Floyd-Warshall: All-Pairs Shortest Paths
- Network Delay Time and Path Reconstruction