chapter

Minimum Spanning Trees and Shortest Paths PYQs for GATE CS

Solve 10+ Minimum Spanning Trees and Shortest Paths previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

2026 Slot Set2 PYQ

Level 4: Challenger

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 ?

Question 2

2026 Slot Set1 PYQ

Let G (V, E) be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of G is/are true?

Question 3

2026 Slot Set1 PYQ

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 \geq 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 \geq 0 and u \in V, d_{k + 1} (u) \leq 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 \geq 0, d_{k} (u) \leq d_{k} (v) . Which one of the following options is correct?

Question 4

2025 Slot Set2 PYQ

Level 4: Challenger

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?

Question 5

2025 Slot Set1 PYQ

Let G be any undirected graph with positive edge weights, and T be a minimum spanning tree of G . For any two vertices, u and v, let d_{1} (u, v) and d_{2} (u, v) be the shortest distances between u and v in G and T, respectively. Which ONE of the options is CORRECT for all possible G, T, u and v ?

Question 6

2025 Slot Set1 PYQ

The maximum value of x such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is ________ . (answer in integer) A B D C 768 x 31

Question 7

2024 Slot Set2 PYQ

Level 4: Challenger

The number of distinct minimum-weight spanning trees of the following graph is __________a b f g c e d 121332222211

Question 8

2022 PYQ

Level 4: Challenger

Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?

Question 9

2021 Slot Set2 PYQ

Let G be a connected undirected weighted graph. Consider the following two statements. S_{1} : There exists a minimum weight edge in G which is present in every minimum spanning tree of G . S_{2} : If every edge in G has distinct weight, then G has a unique minimum spanning tree. Which one of the following options is correct?

Question 10

2021 Slot Set1 PYQ

Level 4: Challenger

Consider the following undirected graph with edge weights as shown: 0.1 0.1 0.1 0.9 0.9 0.1 0.9 0.1 0.9 0.1 0.9 0.1 The number of minimum-weight spanning trees of the graph is __________.

Free preview ends here

Login to view the complete previous-year questions and solutions

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Minimum Spanning Trees and Shortest Paths PYQs for GATE CS

Solve 10+ Minimum Spanning Trees and Shortest Paths previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Journey: Minimum Spanning Trees and Shortest Paths

Chapter Roadmap

Your journey through graph optimization algorithms.

MST Cut-Cycle Properties and Uniqueness

The theoretical foundation. (You are here)

MST Construction and Counting

Kruskal's, Prim's, and counting distinct trees.

Shortest-Path Properties and Algorithms

Dijkstra, Bellman-Ford, and path relaxations.

Effects of Edge-Weight Transformations

Adding constants, scaling, and structural impacts.

MST Cut-Cycle Properties and Uniqueness

Algorithms › Minimum Spanning Trees

Cut-Cycle Properties & Uniqueness

The theoretical engine behind every MST algorithm.

What you will master:

Defining cuts and cycles in graph theory.
The Cut Property: identifying "safe" edges.
The Cycle Property: identifying "unsafe" edges.
Conditions that guarantee a unique Minimum Spanning Tree.

Minimum Spanning Trees and Shortest Paths: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Algorithms · 2026_Set2 MCQ

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$ ?

A.
$Θ (m + n)$
B.
$Θ (m + n lo g (n))$
C.
$Θ (nm)$
D.
$Θ (n^{3})$

Correct Answer:

Step-by-Step Solution

Key idea: Shortest paths in a Directed Acyclic Graph (DAG) can be found in linear time using topological sorting.

Step 1: Recognize that the graph is a DAG. This is the crucial condition that allows a faster algorithm than Dijkstra's or Bellman-Ford.

Step 2: Perform a topological sort of the vertices. This takes $Θ (m + n)$ time using DFS or Kahn's algorithm.

Step 3: Initialize the distance to the source vertex $s$ as 0, and all other vertices as $\infty$ .

Step 4: Process each vertex $u$ in topological order. For each outgoing edge $(u, v)$ with weight $w$ , relax the edge: if $d i s t [v] > d i s t [u] + w$ , update $d i s t [v] = d i s t [u] + w$ .

Step 5: Since each vertex and each edge is processed exactly once in the topological order, the relaxation step takes $Θ (m + n)$ time.

Answer: $Θ (m + n)$

Question 2 · Algorithms · 2026_Set1 MSQ

Let

G (V, E)

be a simple, undirected, edge-weighted graph with unique edge weights.

Which of the following statements about the minimum spanning trees (MST) of

G

is/are true?

A.
In every cycle $C$ of $G$ , the edge with the largest weight in $C$ is not in any MST
B.
In every cycle $C$ of $G$ , the edge with the smallest weight in $C$ is in every MST
C.
For every vertex $v \in V$ , the edge with the largest weight incident on $v$ is not in any MST
D.
For every vertex $v \in V$ , the edge with the smallest weight incident on $v$ is in every MST

Question 3 · Algorithms · 2026_Set1 MCQ

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 \geq 0

, let

d_{k} (u)

denote the weight of a shortest path (in terms of weight) from

s

u

of length at most

k

. If there is no path from

s

u

of length at most

k

, then

d_{k} (u) = \infty

.

Consider the statements:

S1: For every

k \geq 0

and

u \in V

d_{k + 1} (u) \leq 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

v

, then for every

k \geq 0

d_{k} (u) \leq d_{k} (v)

.

Which one of the following options is correct?

A.
Only S1 is true
B.
Only S2 is true
C.
Both S1 and S2 are true
D.
Neither S1 nor S2 is true

Question 4 · Algorithms · 2025_Set2 MCQ

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?

A.
Every MST remains an MST, and every SP remains an SP.
B.
MSTs need not remain MSTs, and every SP remains an SP.
C.
Every MST remains an MST, and SPs need not remain SPs.
D.
MSTs need not remain MSTs, and SPs need not remain SPs.

Correct Answer:

Step-by-Step Solution

Key idea: Adding a constant to all edge weights affects paths and spanning trees differently based on the number of edges.

Step 1: Analyze the effect on Minimum Spanning Trees (MSTs). Every spanning tree of a graph with $V$ vertices has exactly $V - 1$ edges. If a constant $α$ is added to every edge, the total weight of any spanning tree increases by exactly $(V - 1) α$ . Since this increase is uniform for all spanning trees, their relative weight ordering remains unchanged. Thus, every MST remains an MST.

Step 2: Analyze the effect on Shortest Paths (SPs). A path's total weight increases by $k α$ , where $k$ is the number of edges in the path. A previously shortest path with many edges might see its weight increase more than an alternative path with fewer edges but a slightly higher original weight. Thus, shortest paths need not remain shortest paths.

Answer: Every MST remains an MST, and SPs need not remain SPs.

Question 5 · Algorithms · 2025_Set1 MCQ

Let $G$ be any undirected graph with positive edge weights, and $T$ be a minimum spanning tree of $G$ . For any two vertices, $u$ and $v$ , let $d_{1} (u, v)$ and $d_{2} (u, v)$ be the shortest distances between $u$ and $v$ in $G$ and $T$ , respectively. Which ONE of the options is CORRECT for all possible $G$ , $T$ , $u$ and $v$ ?

A.
$d_{1} (u, v) = d_{2} (u, v)$
B.
$d_{1} (u, v) \leq d_{2} (u, v)$
C.
$d_{1} (u, v) \geq d_{2} (u, v)$
D.
$d_{1} (u, v) \neq = d_{2} (u, v)$

Question 6 · Algorithms · 2025_Set1 NAT

The maximum value of

x

such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is ________ . (answer in integer)

Question 7 · Algorithms · 2024_Set2 NAT

The number of distinct minimum-weight spanning trees of the following graph is __________

Correct Answer:

Step-by-Step Solution

Key idea: Use Kruskal's algorithm to group edges by weight and count the number of valid ways to connect the resulting components.

Step 1: List all edges grouped by weight.

Weight 1: (a,b), (a,f), (c,d), (e,d) $\to$ 4 edges.

Weight 2: (a,g), (b,g), (f,g), (g,c), (g,e), (g,d) $\to$ 6 edges.

Weight 3: (b,c), (f,e) $\to$ 2 edges.

Step 2: Process weight 1 edges. They form two disjoint tree components without cycles:

Component 1: {a, b, f} (using edges a-b, a-f)
Component 2: {c, d, e} (using edges c-d, e-d)

Vertex {g} is isolated. Total components = 3.

Step 3: A spanning tree for 7 vertices requires exactly $7 - 1 = 6$ edges. We already have 4 edges of weight 1. We need exactly 2 more edges to connect the 3 components.

Step 4: Look at weight 2 edges. They connect {g} to Component 1 via 3 edges: (a,g), (b,g), (f,g). They connect {g} to Component 2 via 3 edges: (g,c), (g,e), (g,d).

There are no weight 2 edges directly between Component 1 and Component 2.

Step 5: To connect all 3 components, we must choose exactly one edge from the first group (3 choices) and exactly one edge from the second group (3 choices).

Step 6: Total distinct MSTs = $3 \times 3 = 9$ . (Weight 3 edges are not needed as the graph is already connected with weight 1 and 2 edges).

Answer: 9

Question 8 · Algorithms · 2022 MSQ

Consider a simple undirected weighted graph $G$ , all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of $G$ is/are TRUE?

A.
The edge with the second smallest weight is always part of any minimum spanning tree of $G$ .
B.
One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of $G$ .
C.
Suppose $S \subseteq V$ be such that $S \neq = ϕ$ and $S \neq = V$ . Consider the edge with the minimum weight such that one of its vertices is in $S$ and the other in $V ∖ S$ . Such an edge will always be part of any minimum spanning tree of $G$ .
D.
$G$ can have multiple minimum spanning trees.

Correct Answer:

["A","B","C"]

Step-by-Step Solution

Key idea: Apply the Cut Property and Kruskal's algorithm logic to a graph with strictly distinct edge weights.

Step 1: Analyze the distinct weights condition. Since all edge weights are distinct, the Minimum Spanning Tree (MST) of the graph is strictly unique. This immediately makes the statement "G can have multiple minimum spanning trees" FALSE.

Step 2: Evaluate the smallest edges. Let the edges sorted by weight be $e_{1} < e_{2} < e_{3} < e_{4} \dots$

By Kruskal's algorithm, $e_{1}$ is always included.

Step 3: Evaluate $e_{2}$ . Can $e_{2}$ form a cycle with $e_{1}$ ? No, because a cycle requires at least 3 edges in a simple graph. Thus, $e_{2}$ will never be rejected by Kruskal's and is always in the MST. Statement A is TRUE.

Step 4: Evaluate $e_{3}$ and $e_{4}$ . For an edge to be rejected by Kruskal's, it must form a cycle with edges already in the MST. The only edges smaller than $e_{3}$ are $e_{1}$ and $e_{2}$ . These two edges can form at most one path of length 2 (if they share a vertex). Therefore, they can form a cycle with at most ONE additional edge (which would be $e_{3}$ ).

Step 5: Since $e_{1}$ and $e_{2}$ can only cause the rejection of at most one edge (the one closing their cycle), they cannot cause the rejection of BOTH $e_{3}$ and $e_{4}$ . Thus, at least one of $e_{3}$ or $e_{4}$ must be accepted into the MST. Statement B is TRUE.

Step 6: Evaluate the cut property. The statement describes exactly the Cut Property: the minimum weight edge crossing any cut $(S, V ∖ S)$ is always part of the MST. Since weights are distinct, this minimum is unique. Statement C is TRUE.

Answer: A, B, C

Question 9 · Algorithms · 2021_Set2 MCQ

Let

G

be a connected undirected weighted graph. Consider the following two statements.

S_{1} :

There exists a minimum weight edge in

G

which is present in every minimum spanning tree of

G

S_{2} :

If every edge in

G

has distinct weight, then

G

has a unique minimum spanning tree.

Which one of the following options is correct?

A.
Both $S_{1}$ and $S_{2}$ are true.
B.
$S_{1}$ is true and $S_{2}$ is false.
C.
$S_{1}$ is false and $S_{2}$ is true.
D.
Both $S_{1}$ and $S_{2}$ are false.

Question 10 · Algorithms · 2021_Set1 NAT

Consider the following undirected graph with edge weights as shown:

The number of minimum-weight spanning trees of the graph is __________.

Correct Answer:

Step-by-Step Solution

Key idea: Use Kruskal's algorithm to find the MST, grouping edges by weight and counting the number of valid choices at each step.

Step 1: Identify all edges and their weights. The graph is a $3 \times 3$ grid.

Weight 0.1 edges (7 total): Top row horizontal (2), middle row left horizontal (1), bottom row right horizontal (1), left column bottom vertical (1), middle column bottom vertical (1), right column bottom vertical (1).

Weight 0.9 edges (5 total): The remaining edges.

Step 2: Process weight 0.1 edges. These 7 edges connect the 9 vertices into exactly 2 connected components without forming any cycles:

Component 1: Top row (3 vertices, connected by 2 horizontal edges).
Component 2: The remaining 6 vertices, connected by the other 5 weight 0.1 edges in a tree structure.

Step 3: To form a spanning tree of the 9 vertices, we need exactly $9 - 1 = 8$ edges. We already have 7 edges of weight 0.1. We need exactly 1 more edge to connect Component 1 and Component 2.

Step 4: Identify the edges connecting Component 1 and Component 2. These are the 3 vertical edges in the top half of the grid, all of which have weight 0.9.

Step 5: We can choose any 1 of these 3 edges to complete the MST. Each choice yields a valid MST of weight $7 \times 0.1 + 1 \times 0.9 = 1.6$ .

Answer: 3

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Minimum Spanning Trees and Shortest Paths PYQs for GATE CS

Chapter Journey: Minimum Spanning Trees and Shortest Paths

Chapter Roadmap

MST Cut-Cycle Properties and Uniqueness

Cut-Cycle Properties & Uniqueness

Minimum Spanning Trees and Shortest Paths: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit