Algorithms · Shortest Paths
Official IIT answer key · IIT Roorkee · Audited Aug 2026
GATE CSE 2026 Set 2 Q37 · MCQ · 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 →Let G be a weighted directed acyclic graph with m edges and n vertices. Given G and a source vertex s in G, which one of the following options gives the worst case time complexity of the fastest algorithm to find the lengths of shortest paths from s to all vertices that are reachable from s in G?
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.
