Bellman-Ford questions test relaxation, not just Dijkstra's greedy shortcut. The algorithm handles negative edge weights, detects a negative cycle only when the source can reach it, and on a complete graph its O(VE) works out to Θ(n³), not Θ(n²).
KnowledgeGate's question bank holds about 45 Bellman-Ford questions. Twelve are below, and six of those carry previous-year attributions: GATE 2009 and 2013, UGC NET August 2016, December 2019 and June 2025, and BPSC 2024. Attempt each one before reading the answer, then work through the rest of the set in the Algorithms learn module.
Bellman-Ford's paradigm: single source, dynamic programming
Bellman-Ford finds shortest paths from one source to every reachable vertex, unlike all-pairs Floyd-Warshall. It builds answers for paths of at most k edges from paths of at most k-1 edges, making it dynamic programming rather than greedy. The dynamic programming primer develops this idea.
Q1. What does Bellman-Ford find?
The Bellman-Ford algorithm is used to:
(a) Find the shortest path from a single source to all other vertices
(b) Find the shortest path between every pair of vertices
(c) Find if there are any cycles in the graph
(d) Find the maximum weight edge in the graph
Answer: (a)
It is a single-source algorithm, so one source produces all reachable distances. Option (b) describes Floyd-Warshall. DFS handles general cycle detection; Bellman-Ford flags only reachable negative cycles. Option (d) needs just an edge scan.
Q2. Which design paradigm does it use? (BPSC 2024)
Bellman Ford algorithm is an example for ______.
(a) Linear Programming
(b) Greedy Algorithms
(c) Dynamic Programming
(d) More than one of the above
(e) None of the above
Answer: (c)
After pass k, distances are correct among paths using at most k edges, so the method builds from smaller subproblems. Greedy finalisation is unsafe with negative weights. Options (d) and (e) follow BPSC's five-option style.
Q3. Which algorithms are greedy? (UGC NET June 2025)
Which of the following algorithms use Greedy strategy?
A. Dijkstra's algorithm
B. Kruskal's algorithm
C. Huffman coding
D. Bellman-Ford algorithm
Choose the correct answer from the options given below:
(a) A, B and D Only
(b) A, B and C Only
(c) C and D Only
(d) A and D Only
Answer: (b)
Dijkstra chooses the closest unfinalised vertex, Kruskal the lightest safe edge, and Huffman the two least-frequent symbols. Bellman-Ford keeps re-relaxing instead of committing. This tests Q2's distinction in reverse.
Relaxation with actual numbers
Relaxation asks one question at every edge: is d[u] + w(u,v) smaller than d[v]? If it is, d[v] drops to that sum. No vertex is ever locked in, which is what lets negative edges be handled safely later.
Q4. Update one distance (UGC NET December 2019)
Consider a weighted directed graph. The current shortest distance from source S to node x is represented by d[x]. Let d[v]=29, d[u]=15, w[u,v]=12. What is the updated value of d[v] based on current information?
(a) 29
(b) 27
(c) 25
(d) 17
Answer: (b)
Apply d[v] = min(29, 15 + 12) = min(29, 27) = 27. Option (d) wrongly uses 29 - 12, while (c) follows no valid relaxation.
![Relaxation example updating d[v] from 29 to 27 using d[u]=15 and edge weight w(u,v)=12.](https://cdn.knowledgegate.ai/blog-assets/blog_asset_1784133933894_ltp597.jpg)
Passes and time complexity
Bellman-Ford relaxes all E edges for V-1 passes, giving O(VE). A simple shortest path without a negative cycle uses at most V-1 edges, so those passes are sufficient.
Q5. How many times is each edge relaxed?
For a graph with V vertices, how many times does each edge need to be relaxed in the worst case in Bellman-Ford algorithm?
(a) 1
(b) V
(c) V-1
(d) V+1
Answer: (c)
Each edge is relaxed once in each of V-1 main passes. The optional V-th pass only checks for a further improvement, which reveals a reachable negative cycle.
Q6. What is the general time complexity?
What is the time complexity of the Bellman-Ford algorithm, where V is the number of vertices and E is the number of edges?
(a) O(V²)
(b) O(V + E)
(c) O(V·E)
(d) O(E log V)
Answer: (c)
The work is (V-1)E, hence O(VE). O(V + E) belongs to BFS on an unweighted graph, O(V²) can describe array-based Dijkstra, and O(E log V) points to heap-based Dijkstra.
Q7. What happens on a complete graph? (GATE 2013)
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
(a) Θ(n²)
(b) Θ(n² log n)
(c) Θ(n³)
(d) Θ(n³ log n)
Answer: (c)
A complete graph has E = n(n-1)/2 edges. At n = 5, this is 5(4)/2 = 10. Therefore E is Θ(n²), and Θ(VE) = Θ(n · n²) = Θ(n³). The logarithmic options mimic heap-based Dijkstra. Practise the exact GATE 2013 solved question.
Negative edge weights
Negative weights can break Dijkstra's greedy finalisation. Bellman-Ford never finalises early, so negative edges are fine. Only a reachable negative cycle is fatal because every lap lowers the cost. The BFS, DFS and shortest-path overview provides the Dijkstra baseline.
Q8. Which edge weights are allowed?
The Bellman-Ford algorithm can handle which of the following edge-weight types, provided there is no reachable negative-weight cycle?
(a) Positive
(b) Negative
(c) Zero
(d) All of the above
Answer: (d)
Relaxation assumes nothing about an edge's sign, so all three types work. The proviso matters because another lap around a reachable negative cycle always lowers the cost.
Q9. Which algorithm handles positive and negative weights?
In a directed graph with positive and negative edge weights, which of the following algorithms can find the shortest path from a single source to all other vertices?
(a) Dijkstra's Algorithm
(b) Bellman-Ford Algorithm
(c) Both (a) and (b)
(d) None of the above
Answer: (b)
Take vertices S, a and b, with S to a of weight 4, S to b of weight 5, and b to a of weight -3. Dijkstra can settle a at 4, but S to b to a costs 5 + (-3) = 2. Bellman-Ford revisits the edge and finds 2.
Negative cycles and the extra pass
After V-1 passes, scan every edge once more. Any improvement proves a reachable negative cycle. A cycle in a disconnected component remains invisible because its vertices never receive finite distances from the source.
Q10. What cycle does Bellman-Ford detect? (GATE 2009)
Which of the following statement(s) is / are correct regarding Bellman-Ford shortest path algorithm?
P: Always finds a negative weighted cycle, if one exists.
Q: Finds whether any negative weighted cycle is reachable from the source.
(a) P Only
(b) Q Only
(c) Both P and Q
(d) Neither P nor Q
Answer: (b)
P is false because an unreachable negative cycle is invisible. Q is the precise guarantee: an improvement during the V-th scan proves a reachable negative cycle. Confirm it on the exact GATE 2009 solved question.
Q11. What is the total detection time?
The Bellman-Ford algorithm takes ___ time to detect the presence of a negative weight cycle in a graph.
(a) O(E)
(b) O(V²)
(c) O(VE)
(d) None of the above
Answer: (c)
The last scan costs O(E), but the preceding passes cost O((V-1)E). Together they cost O(VE). Option (a) counts only the final scan.
Matching Bellman-Ford with its neighbours
Lock in Bellman-Ford at O(VE) and Floyd-Warshall at O(V³), then eliminate options.
Q12. Match each algorithm to its complexity (UGC NET August 2016)
Match the following algorithm with its standard time complexity:
Algorithms:
a. Prim's algorithm
b. Bellman-Ford algorithm
c. Floyd-Warshall algorithm
d. Johnson's algorithm
Complexities:
i. O(VE)
ii. O(VE log V)
iii. O(E log V)
iv. O(V³)
Here, V is the set of vertices and E is the set of edges in the graph. Choose the correct matching.
(a) a-i, b-iii, c-iv, d-ii
(b) a-i, b-iii, c-ii, d-iv
(c) a-iii, b-i, c-iv, d-ii
(d) a-iii, b-i, c-ii, d-iv
Answer: (c)
Bellman-Ford gives b-i, and Floyd-Warshall's three loops give c-iv. Prim with a binary heap gives a-iii. Johnson runs Bellman-Ford once, then Dijkstra from every vertex, giving d-ii in this question. Fixing b-i removes (a) and (b); c-iv removes (d).
The short version and your next step
Bellman-Ford solves single-source shortest paths using dynamic programming, not a greedy commitment.
It relaxes every edge for V-1 passes, takes O(VE), and takes Θ(n³) on a complete graph.
Positive, zero, and negative edges are valid, but a reachable negative cycle means no finite shortest path exists.
The whole update is d[v] = min(d[v], d[u] + w(u,v)).
One extra edge scan detects reachable negative cycles, and neighbouring algorithm complexities help with matching questions.
The GATE 2009 and GATE 2013 questions are solved in full inside GATE Guidance by Sanchit Sir. Revisit whichever ones you missed, then browse the wider GATE CS preparation options.
