1
GATE CSE 2012
MCQ (Single Correct Answer)
+2
-0.6
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered. GATE CSE 2012 Algorithms - Greedy Method Question 14 English
A
SDT
B
SBDT
C
SACDT
D
SACET
2
GATE CSE 2011
MCQ (Single Correct Answer)
+2
-0.6
An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 ,….vn. Two nodes vi , vj are connected if and only if 0 < |i – j| <= 2. Each edge (vi, vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below. GATE CSE 2011 Algorithms - Greedy Method Question 16 English What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?
A
$${1 \over {12}}(11{n^2} - 5n)$$
B
$${n^2}{\rm{ - }}\,n + 1$$
C
6n – 11
D
2n + 1
3
GATE CSE 2011
MCQ (Single Correct Answer)
+2
-0.6
An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 ,….vn. Two nodes vi , vj are connected if and only if 0 < |i – j| <= 2. Each edge (vi, vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below. GATE CSE 2011 Algorithms - Greedy Method Question 15 English The length of the path from v5 to v6 in the MST of previous question with n = 10 is
A
11
B
25
C
31
D
41
4
GATE CSE 2010
MCQ (Single Correct Answer)
+2
-0.6
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W(ij) in the matrix W below is the weight of the edge {i, j}. $$$w = \left( {\matrix{ 0 & 1 & 8 & 1 & 4 \cr 1 & 0 & {12} & 4 & 9 \cr 8 & {12} & 0 & 7 & 3 \cr 1 & 4 & 7 & 0 & 2 \cr 4 & 9 & 3 & 2 & 0 \cr } } \right)$$$ What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?
A
7
B
8
C
9
D
10
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
CBSE
Class 12