GATE CS 2026 (Forenoon) — Question 41

AlgorithmsGraph Traversals (BFS, DFS) & Single-Source Shortest PathsMCQ2 marks · −2/3 if wrongHard

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 \( s \in V \) be a vertex in \( G \). For every \( u \in V \) and for every \( k \ge 0 \), let \( d_k(u) \) denote the weight of a shortest path (in terms of weight) from \( s \) to \( u \) of length at most \( k \). If there is no path from \( s \) to \( u \) of length at most \( k \), then \( d_k(u) = \infty \). Consider the statements: S1: For every \( k \ge 0 \) and \( u \in V \), \( d_{k+1}(u) \le d_k(u) \). S2: For every \( (u, v) \in E \), if \( (u, v) \) is part of a shortest path (in terms of weight) from \( s \) to \( v \), then for every \( k \ge 0 \), \( d_k(u) \le d_k(v) \). Which one of the following options is correct?
  1. A
    Only S1 is true
  2. B
    Only S2 is true
  3. C
    Both S1 and S2 are true
  4. D
    Neither S1 nor S2 is true
Practise the full 2026-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAWhat rank do your marks get?GATE score, likely All-India Rank and qualifying marks for your category.
Practise more on Graph Traversals (BFS, DFS) & Single-Source Shortest PathsTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group