Algorithms · Minimum Spanning Trees and Shortest Paths
Official IIT answer key · IIT Guwahati · Audited Aug 2026
GATE CSE 2025 Set 2 Q37 · MCQ · 2 marks
Key concept
No account needed
Sit 1 related Minimum Spanning Trees and 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
GATE tests the fundamental invariant properties of Minimum Spanning Trees (MSTs) and Shortest Paths (SPs) under edge-weight modifications. Questions assess whether structural properties—such as the fixed number of edges in any spanning tree (|V|-1) versus variable edge counts in different path alternatives—preserve or alter optimal subgraphs when weights undergo transformations like additive shifts or scaling.
Full Minimum Spanning Trees and Shortest Paths guide →Let G be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in G before and after the edge weight update?
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.
