Bellman-Ford Algorithm Interview Questions: Model Answers and a Worked Trace
Learn Bellman-Ford as an interview explanation, not a memorised recipe. Trace a fixed edge order, diagnose a reachable negative cycle and test robust code.
KnowledgeGate Team
Exam prep & CS education

Memorising “relax every edge V-1 times” is not enough when an interviewer changes one weight, asks why V-1 passes suffice, or checks whether a negative cycle is reachable from the source. A strong answer connects the rule to its invariant, traces updates, detects a reachable negative cycle, and states implementation guardrails.
Bellman-Ford in a 60-second interview answer
Bellman-Ford computes single-source shortest-path distances in a weighted directed graph, permits negative weights, and reports a negative-weight cycle reachable from the source. Initialise the source to 0, others to infinity. Relax every edge for at most |V|-1 passes, then scan once more for a strict improvement.
Why V-1? Without a source-reachable negative cycle, a shortest simple path has at most |V|-1 edges. After pass i, distances are correct for shortest paths using at most i edges. In-place relaxation may propagate farther and converge earlier depending on edge order.
BFS suits unweighted or unit-weight paths. Dijkstra is usually faster but requires non-negative weights. Bellman-Ford trades speed for negative-edge support and reachable negative-cycle detection. Compare them in Graph Algorithms: BFS, DFS and Dijkstra Traced Step by Step.
Work the five-vertex relaxation trace exactly
For source S on vertices S, A, B, C, D, use edges S->A=4, S->B=5, A->C=-3, B->C=2, C->D=3 and D->B=-1. The deliberately unfavourable order is D->B, C->D, B->C, A->C, S->B, S->A. Edge order affects intermediate values, not correctness.
state | d(S) | d(A) | d(B) | d(C) | d(D) | updates that survive at pass end |
|---|---|---|---|---|---|---|
Initial | 0 | infinity | infinity | infinity | infinity | none |
After pass 1 | 0 | 4 | 5 | infinity | infinity |
|
After pass 2 | 0 | 4 | 5 | 1 | infinity |
|
After pass 3 | 0 | 4 | 5 | 1 | 4 |
|
After pass 4 | 0 | 4 | 3 | 1 | 4 |
|
Extra scan | 0 | 4 | 3 | 1 | 4 | no strict improvement |
Initially, only the source is defined and no predecessor is set. In pass 2, B->C offers 5+2=7, then A->C improves it to 4+(-3)=1, so C<-A survives. Pass 3 gives D<-C because 1+3=4; pass 4 gives B<-D because 4+(-1)=3. The quiet scan means no reachable negative-weight cycle. The original cycle weighs 2+3+(-1)=4, not negative.
The final predecessors are A<-S, C<-A, D<-C and B<-D. Following them backwards and reversing gives S->A->C->D->B, with cost 4+(-3)+3+(-1)=3.

Explain the implementation, invariant and complexity
Put the finite-source guard before addition:
dist[S] = 0; all others = infinity
for pass 1 through |V|-1:
updated = false
for each (u, v, w):
if dist[u] is finite and dist[u] + w < dist[v]:
dist[v] = dist[u] + w; parent[v] = u; updated = true
if not updated: stop
scan once more with the same guard
if a strict improvement exists: report a reachable negative cycleEvery finite dist[v] is a discovered source-to-v walk cost, so it is an upper bound on the true shortest distance. Relaxation only lowers it. The |V|-1 simple-path argument ensures completion when no reachable negative cycle exists.
With an edge list, worst-case time is O(VE). Distance and parent arrays use O(V) auxiliary space, excluding graph storage. Early stopping does not change the worst case. Use a wide numeric type and test finiteness before addition.
Detect a reachable negative cycle by changing one value
Change only D->B from -1 to -6. The reachable cycle B->C->D->B now weighs 2+3+(-6)=-1. With the same order and all other weights unchanged, pass four ends at [S=0,A=4,B=-2,C=0,D=4]. Because the cycle is reachable from S through B, its reductions remain eligible under the finite-source guard on later passes.
On the extra scan, D->B offers 4+(-6)=-2, equal to current B, so it does not improve. Next, C->D offers 0+3=3, below D=4. That strict improvement reports a reachable negative cycle. Repeated turns around a cycle weighing -1 reduce costs to B, C and D without bound, so they have no finite shortest-path values.
Standard single-source Bellman-Ford ignores negative cycles in source-unreachable components because their edges fail the finite-source guard. To detect any negative cycle, add a super-source with zero-weight edges to every vertex. Equivalent all-zero initialisation works with the appropriate full-graph cycle test.

Bellman-Ford interview questions with model answers
Use these compact model answers:
question | model answer |
|---|---|
Why exactly | A simple path uses at most |
Can Bellman-Ford stop early? | Yes, after a full pass with no update. |
Can it handle negative edges? | Yes, unless a reachable negative cycle makes a distance unbounded. |
Why not use Dijkstra here? | A negative edge violates Dijkstra's non-negative-weight correctness condition. |
How do you reconstruct | Follow |
Does an unreachable negative cycle matter to this source? | Not to standard single-source detection. |
Can you recover the cycle? | Store predecessors. After a detection-pass update, walk back |
In an undirected graph represented by both directions, a reachable negative edge creates a negative two-edge closed walk if traversal can repeat. Shortest walks in that component are not finite. For broader follow-up practice, use DSA Interview Questions: 7 Patterns for Placements.
Coding traps and exact tests that expose them
Adding to infinity or overflowing a narrow integer can cause false relaxation. Guard dist[u] and use a wide type. Omitting the extra scan misses cycle detection. Flagging any cycle causes false alarms, so require a strict relaxable inequality. Assuming one-pass convergence creates an edge-order bug, so keep V-1 passes unless a full pass is quiet.
Test the implementation systematically against these exact outcomes:
The main graph returns
[0,4,3,1,4]and pathS,A,C,D,B.The
D->B=-6variant reports a reachable negative cycle.Edges
S->A=2andB->C=-5leaveB,Cunreachable and report no source-reachable cycle.Parallel edges
S->A=7andS->A=2returnd(A)=2.One vertex
Swith no edges returns0and no cycle.
For more practice, use Bellman-Ford Algorithm MCQs: 12 Solved and Explained as the next trace-and-concept check.
How short screens and deeper rounds can probe the same idea
For a short-screen response, define the problem, state V-1 relaxation passes plus one detection scan, give O(VE) time and O(V) auxiliary space, then contrast Bellman-Ford's negative-edge support with Dijkstra.
Use this sequence to rehearse the definition, invariant, trace, cycle test and implementation details in order. Broader placement practice is available through the Resume & Interview Preparation category.
The short version and next coding step
Recall: single source -> initialise infinity -> relax every directed edge up to V-1 times -> stop early only after a quiet pass -> scan once more for a reachable negative cycle. Here, d=[0,4,3,1,4], path S->A->C->D->B, cost 3, and worst-case time O(VE).
Redraw both variants, predict each pass, then implement distance, parent and cycle outputs. Choose DSA Using Java for DSA or Coding for Placements for multi-language practice.
Keep learning
Bellman-Ford Algorithm MCQs: 12 Solved Questions with Explanations
Solve 12 Bellman-Ford MCQs with concise explanations, worked relaxation and complexity calculations, and previous-year question links.
Shortest Path Algorithms: Dijkstra, Bellman-Ford and Floyd-Warshall with Worked Examples for GATE CS
Learn the relaxation idea behind shortest paths, trace three core algorithms by hand, and choose the right method from edge weights and source count.
Kruskal's Algorithm Interview Questions: MST Traces, DSU and Model Answers
Trace Kruskal's algorithm on a six-vertex graph, then rehearse model answers on DSU, correctness, complexity, ties, negative weights and disconnected inputs.
MST and Prim's Algorithm Interview Questions: Model Answers and Worked Traces
Build an interview-ready understanding of minimum spanning trees and Prim's algorithm through an exact trace, correctness proof, Kruskal comparison and edge-case checks.





