ExamSIDE.Com

# GATE CSE 2006 Question

Signle Correct Answer
Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that the weight of the edge (vi, vj) is $2|i-j|$. The weight of a minimum spanning tree of G is:
A
n — 1
B
2n — 2
C
${n \over 2}$
D
$n^2$

# GATE CSE 2006 Question

Signle Correct Answer
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:
A
Queue
B
Stack
C
Heap
D
B-Tree

# GATE CSE 2016 Set 1 Question

Signle Correct Answer
Let $G$ be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?

$P:$ Minimum spanning tree of $G$ does not change
$Q:$ Shortest path between any pair of vertices does not change

A
$P$ only
B
$Q$ only
C
Neither $P$ nor $Q$
D
Both $P$ and $Q$