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

Updated 11 Nov 20265 min read
Bellman-Ford Algorithm Interview Questions: Model Answers and a Worked Trace

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

B<-S, A<-S

After pass 2

0

4

5

1

infinity

C<-A

After pass 3

0

4

5

1

4

D<-C

After pass 4

0

4

3

1

4

B<-D

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.

Directed five-vertex graph with weighted edges and a relaxation table showing Bellman-Ford distances after four passes and final path S to A to C to D to B.

Explain the implementation, invariant and complexity

Put the finite-source guard before addition:

Code
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 cycle

Every 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.

Directed graph with reachable negative cycle B to C to D to B, changed edge weight minus 6, pass-four distances, and strict-improvement detection.

Bellman-Ford interview questions with model answers

Use these compact model answers:

question

model answer

Why exactly V-1 passes?

A simple path uses at most V-1 edges.

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 S to B?

Follow B<-D<-C<-A<-S, then reverse the sequence.

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 V times to enter the cycle, then continue until a vertex repeats.

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:

  1. The main graph returns [0,4,3,1,4] and path S,A,C,D,B.

  2. The D->B=-6 variant reports a reachable negative cycle.

  3. Edges S->A=2 and B->C=-5 leave B,C unreachable and report no source-reachable cycle.

  4. Parallel edges S->A=7 and S->A=2 return d(A)=2.

  5. One vertex S with no edges returns 0 and 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.