GATE 2026 · CS1 - Forenoon
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 ≥ 0, let dk(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 dk(u) = ∞.
Consider the statements:
S1: For every k ≥ 0 and u in V, dk+1(u) ≤ dk(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 ≥ 0, dk(u) ≤ dk(v).
Which one of the following options is correct?