Crack
GATE
C
G
Topic
Shortest Paths
Algorithms
0
/ 3 done
Questions per paper
All
MCQ
MSQ
NAT
2015 to 2026. Point at a year to read it.
0
1
2015
2019
2021
2023
2025
2026
Show as a table
Year
All
MCQ
MSQ
NAT
2015
0
0
0
0
2018
0
0
0
0
2019
0
0
0
0
2020
1
1
0
0
2021
0
0
0
0
2022
0
0
0
0
2023
0
0
0
0
2024
0
0
0
0
2025
0
0
0
0
2026
1
1
0
0
1
CS 2026 Set 1 · 2 marks · MCQ · Moderate
Let
G
(
V
,
E
)
G(V, E)
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.
2
CS 2026 Set 2 · 2 marks · MCQ · Moderate
Let
G
G
G
be a weighted directed acyclic graph with
m
m
m
edges and
n
n
n
vertices. Given
G
G
G
and a source vertex
s
s
s
in
G
G
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
s
s
to all vertices that are reachable from
s
s
s
in
G
G
G
?
3
CS 2020 · 2 marks · MCQ · Hard
Let
G
=
(
V
,
E
)
G = (V, E)
G
=
(
V
,
E
)
be a directed, weighted graph with weight function
w
:
E
→
R
w : E \to \mathbb{R}
w
:
E
→
R
. For some function
f
:
V
→
R
f : V \to \mathbb{R}
f
:
V
→
R
, for each edge
(
u
,
v
)
∈
E
(u, v) \in E
(
u
,
v
)
∈
E
, define
w
′
(
u
,
v
)
w'(u, v)
w
′
(
u
,
v
)
as
w
(
u
,
v
)
+
f
(
u
)
−
f
(
v
)
w(u, v) + f(u) - f(v)
w
(
u
,
v
)
+
f
(
u
)
−
f
(
v
)
.