Algorithms · Shortest Paths
Official IIT answer key · IISc Bangalore · Audited Aug 2026
GATE CSE 2016 Set 1 Q38 · NAT · 2 marks
Key concept
No account needed
Sit 4 related Shortest PathsPYQs as a guest. We'll score the set and show which traps cost marks — sign in only if you want to save the run.
Topic notes
Shortest paths questions in GATE CS consistently assess both procedural graph execution (exact state transitions during relaxation under explicit tie-breaking conditions) and deep structural properties of shortest path algorithms. Across the years, the topic spans algorithm tracing (Dijkstra), graph reweighting principles (Johnson's technique), parametric weight constraints, and optimal algorithmic bounds on specialized topologies (such as DAGs). Questions are invariably weighted at 2 marks, reflecting high conceptual and analytical rigor.
Full Shortest Paths guide →Consider the weighted undirected graph with 4 vertices, where the weight of edge \i, j\ is given by the entry Wij in the matrix W. W = bmatrix 0 & 2 & 8 & 5 \\ 2 & 0 & 5 & 8 \\ 8 & 5 & 0 & x \\ 5 & 8 & x & 0 bmatrix The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is …
Topic-wise GATE CS PYQs with verified steps
Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.
