Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Compute single-source shortest paths when edges may be negative. Relax every edge V − 1 times; after that, all shortest distances are final. One extra relaxation pass that still improves something proves a reachable negative cycle exists. O(V·E).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognize that negative edges rule out Dijkstra, can explain why V − 1 passes suffice, and know the Vth-pass trick for negative-cycle detection.
Where candidates slip
Running fewer than V − 1 passes, omitting the INF guard (overflow), or claiming Dijkstra handles negatives.
How to stand out
Frame each pass as a DP layer over path length, explain the negative-cycle detection cleanly, and contrast O(V·E) with Dijkstra's O((V+E) log V) to justify when each wins.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Bellman-Ford follows negative edges to find dist[4] = -2. Dijkstra would mis-finalize here.
How to read it:0→1→2→0 sums to -1. The Vth relaxation pass still improves, flagging this.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Naive Path Enumeration (Baseline — Don't Ship)
1Hint 1Explore hintHide hint
The literal definition: shortest path = minimum over all simple paths from src to the target. Could you just enumerate them?
2Hint 2Explore hintHide hint
The number of simple paths can be factorial in V — far too many to list.
3Hint 3Explore hintHide hint
You need something that reuses subproblem results instead of re-walking whole paths. That points to dynamic programming over path length.
A · Core idea
The definition of a shortest path invites a brute-force reading: list every simple path from the source to a vertex, sum each one's weights, and keep the minimum.
Why this is the tempting first thought. It is a direct transcription of 'shortest path' — no algorithmic insight required, just enumeration. For a 3- or 4-vertex graph you could even do it by hand.
Why it is hopeless. The number of simple paths between two vertices in a dense graph grows factorially with V. There is no way to enumerate them for even moderate n, and negative edges mean you cannot prune greedily the way you might with positive ones.
What it teaches. The fix is to stop thinking about whole paths and start thinking about path length in edges. If you know the best distance achievable using at most k edges, you can extend to k + 1 edges by relaxing every edge once. That recurrence is exactly Bellman-Ford — the DP that replaces enumeration.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 3, edges = [[0,1,4],[0,2,5],[1,2,-3]], src = 0Array state
paths to 2
0→2 (cost 5) and 0→1→2 (cost 1)
dist[2] = 1 (but this enumeration explodes for larger graphs)C · Code with teaching comments
Reference implementation preview// Illustrative only — exponential, do NOT use beyond tiny graphs. int best = Integer.MAX_VALUE; void enumerate(int u, int target, int cost, boolean[] visited, List<int[]>[] adj) { if (u == target) { best = Math.min(best, cost); return; } visited[u] = true;Explore the full codeHide the full code
D · Why it works and complexityO(V!) worst case timeO(V) spaceOpen the invariant and proofExplore the proofHide the proof
Whenever brute force is 'enumerate all paths', the rescue is almost always a DP indexed by something bounded — here, the number of edges in the path, which is capped at V − 1 for any simple shortest path.
ComplexityO(V!) worst case time, O(V) space — The count of simple paths between two vertices can grow factorially; enumerating each is hopeless beyond tiny graphs.
E · Edge cases and pitfalls2Trying this on anything larger than a handful of vertices — it never finishes.Explore edge casesHide edge cases
Pitfalls
- Trying this on anything larger than a handful of vertices — it never finishes.
- Assuming greedy pruning works — negative edges defeat it.
Approach 2 of 2 · Optimal
Bellman-Ford — V−1 Relaxation Passes + Cycle Check (Optimal)
1Hint 1Explore hintHide hint
Define dist_k[v] = shortest distance to v using at most k edges. What is dist_0? And how do you get dist_{k+1} from dist_k?
2Hint 2Explore hintHide hint
dist_{k+1}[v] = min(dist_k[v], min over edges (u,v,w) of dist_k[u] + w). One pass over all edges performs this extension.
3Hint 3Explore hintHide hint
A simple shortest path has at most V − 1 edges, so V − 1 passes converge. A Vth pass that still improves means a path can keep shrinking — a negative cycle.
A · Core idea
Bellman-Ford is dynamic programming over the number of edges in a path. Let dist_k[v] be the shortest distance from the source to v using at most k edges. Then dist_0[src] = 0 and everything else is infinity, and each relaxation pass turns dist_k into dist_{k+1}.
The recurrence and why one pass implements it. To extend by one edge: dist_{k+1}[v] = min(dist_k[v], min over all edges (u, v, w) of dist_k[u] + w). A single sweep over the entire edge list, doing if dist[u] + w < dist[v]: dist[v] = dist[u] + w, performs exactly this relaxation for every edge. We update dist in place, which only ever helps convergence (a later edge in the same pass can ride on an improvement made earlier in the same pass).
Why V − 1 passes are exactly enough. Any shortest path in a graph with no negative cycle is simple — it visits each vertex at most once — so it has at most V − 1 edges. By induction, after pass k every shortest path using at most k edges is correct. After V − 1 passes, all shortest paths are final. Running more passes would change nothing... unless a negative cycle exists.
The negative-cycle detector. Run one extra (Vth) pass. If any edge still relaxes — dist[u] + w < dist[v] is still true — then there is a path that improves by adding yet another edge beyond the V − 1 bound. The only way that happens is a reachable negative-weight cycle, where looping keeps subtracting cost forever. We report it instead of returning meaningless distances.
The overflow guard. Because unreached vertices hold infinity, we must check dist[u] != INF before computing dist[u] + w; otherwise INF + w overflows (in Java) or pollutes the array. This single guard is the most common silent bug.
Why an edge list, not an adjacency list, is natural here. Bellman-Ford relaxes every edge each pass regardless of order, so a flat edge list is the most direct representation. (You can build it from an adjacency list too; the loop is iterative either way, so there is no recursion and no stack-overflow risk on large graphs.)
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 3, edges = [[0,1,4],[0,2,5],[1,2,-3]], src = 0Array state
init
dist[src]=0
[0, 4, 1]C · Code with teaching comments
D · Why it works and complexityO(V·E) timeO(V) spaceOpen the invariant and proofExplore the proofHide the proof
The clean mental model is 'DP layered by path length'. That single idea explains both the V − 1 bound (longest simple path) and the negative-cycle detector (a Vth improvement is impossible without a cycle). It is also why Bellman-Ford, unlike Dijkstra, never assumes anything about edge signs.
ComplexityO(V·E) time, O(V) space — V − 1 passes, each scanning all E edges → O(V·E). The Vth detection pass is one more O(E). Space is the O(V) dist array (edge list is the input).
E · Edge cases and pitfalls7negative edge but no negative cycle — Distances settle normally; the Vth pass finds no relaxation.Explore edge casesHide edge cases
Edge cases handled
negative edge but no negative cycleDistances settle normally; the Vth pass finds no relaxation.negative cycle not reachable from srcIt never relaxes from src's component, so the Vth pass stays quiet — correctly ignored.disconnected vertexStays at infinity through all passes → reported as -1.
Pitfalls
- Omitting the INF guard so INF + w overflows or corrupts dist.
- Running n passes instead of n − 1 for the main loop, or skipping the detection pass entirely.
- Returning distances when a negative cycle exists instead of reporting undefined.
- Using int instead of long when many negative/positive weights accumulate.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int[] bellmanFord(int n, int[][] edges, int src) { long[] dist = new long[n]; Arrays.fill(dist, Long.MAX_VALUE); dist[src] = 0; Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Missing the overflow guard
Unreached vertices hold a sentinel 'infinity'. Computing infinity + w wraps around in fixed-width integers and produces a bogus 'shorter' distance, corrupting results.
Explore the code comparisonHide the code comparison
Missing the overflow guard
Unreached vertices hold a sentinel 'infinity'. Computing infinity + w wraps around in fixed-width integers and produces a bogus 'shorter' distance, corrupting results.
Don't write this
for (int[] e : edges) {
if (dist[e[0]] + e[2] < dist[e[1]]) { // dist[e[0]] may be MAX_VALUE → overflow
dist[e[1]] = dist[e[0]] + e[2];
}
}Write this instead
for (int[] e : edges) {
if (dist[e[0]] != Long.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {
dist[e[1]] = dist[e[0]] + e[2];
}
}2Not detecting the negative cycle
Without the Vth pass you return whatever the V − 1 passes produced, which is meaningless when a negative cycle lets cost drop without bound.
Explore the code comparisonHide the code comparison
Not detecting the negative cycle
Without the Vth pass you return whatever the V − 1 passes produced, which is meaningless when a negative cycle lets cost drop without bound.
Don't write this
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
return dist # no cycle check!Write this instead
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] != INF and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in edges:
if dist[u] != INF and dist[u] + w < dist[v]:
return [] # negative cycle detected3Wrong pass count
Fewer than V − 1 passes can miss long shortest paths; the bound V − 1 is exactly the maximum edges in a simple path.
Explore the code comparisonHide the code comparison
Wrong pass count
Fewer than V − 1 passes can miss long shortest paths; the bound V − 1 is exactly the maximum edges in a simple path.
Don't write this
for _ in range(n): # one too many for the main loop, and no detection role
for u, v, w in edges:
...Write this instead
for _ in range(n - 1): # main relaxation
...
# separate Vth pass strictly for cycle detectionRevise
Carry the pattern into the interview
Pattern to remember
Repeated edge relaxation (DP over path length)
Code pattern to memorize
dist[src] = 0
repeat V - 1 times:
for (u, v, w) in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Vth pass: any relaxation ⇒ negative cycleRules to remember
- 1Run exactly V − 1 relaxation passes — that is the longest a simple shortest path can be.
- 2Guard relaxation with
dist[u] != INFso you never computeINF + wand overflow. - 3A Vth pass that still relaxes an edge means a reachable negative cycle exists.
- 4Negative edges are fine; only negative cycles make shortest paths undefined.
- 5Add an early
breakwhen a full pass changes nothing — it has already converged.
Use this pattern when
- Single-source shortest path where some edge weights are **negative**
- You must **detect a negative cycle**, which Dijkstra cannot do
- Edge list is given directly and the graph is sparse-to-moderate
- Currency arbitrage, financial graphs, or any cost that can be negative
Choose another pattern when
- All weights non-negative → Dijkstra is O((V+E) log V), much faster
- All-pairs shortest paths needed → Floyd-Warshall O(V³) is cleaner
- Unweighted graph → plain BFS
- Graph is huge and dense → O(V·E) becomes O(V³), reconsider
Interview takeaway
Bellman-Ford is the dynamic-programming view of shortest paths: pass k settles every shortest path of at most k edges. Its superpower over Dijkstra is handling negative edges and detecting negative cycles, paid for with O(V·E) time.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical DP-over-path-length relaxation. Reach for it whenever shortest paths meet negative edges or you must detect a negative cycle. The bounded-pass variant solves hop-limited shortest path (Cheapest Flights Within K Stops), and the −log trick turns it into currency arbitrage detection.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Dijkstra's Shortest PathSame single-source problem with non-negative weights only — O((V+E) log V), much faster.
- Cheapest Flights Within K StopsComing soonBellman-Ford limited to K+1 passes naturally bounds the path to K stops.
- Floyd-Warshall All-PairsAll-pairs version that also tolerates negative edges; detects negative cycles via a negative diagonal.
- Detect Negative Cycle (Currency Arbitrage)Coming soonTake −log of exchange rates; a negative cycle means a profitable arbitrage loop.