GATE CS 2026 Set 1 — Question 41
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MCQ+2 / -0.67HardBellman-Ford AlgorithmGraph AlgorithmsAlgorithms
Algorithms → Graph Algorithms → Bellman-Ford Algorithm
Last updated
Question
Let
G(V, E) be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path.Let be a vertex in . For every and for every , let denote the weight of a shortest path (in terms of weight) from to of length at most . If there is no path from to of length at most , then .Consider the statements:S1: For every and , .S2: For every , if is part of a shortest path (in terms of weight) from to , then for every , .Which one of the following options is correct?Correct answer
(A) Only S1 is true
Solution
Statement S1: is the minimum weight among all paths from to with length . is the minimum weight among all paths with length . Since the set of paths of length is a subset of the set of paths of length , the minimum over the larger set must be less than or equal to the minimum over the subset. Thus, is always true.Statement S2: This statement claims that if is on a shortest path to , then for all . This is false. Consider a graph where the shortest path from to is . It is possible that is reached via a long path (many edges) with low weight, while has a direct high-weight edge from or a short path with high weight. Counter-example:
- Edges: (length 5, weight 10), (length 1, weight 100), (weight 1).
- Shortest path to is (weight ). So is on the shortest path.
- Consider .
- (assuming the path to has length 5).
- (direct edge).
- . Thus S2 is false.
Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Graph Algorithms
2026 Set 1 Q17Consider the following recurrence relations: For all ,…2026 Set 2 Q24Consider the following functions, where is a positive integer.…2026 Set 2 Q25Which of the following can be recurrence relation(s) corresponding to an algorithm with time…2026 Set 2 Q32Consider an array . Suppose the merge sort algorithm is…2026 Set 2 Q37Let be a weighted directed acyclic graph with edges and vertices. Given and a…