GATE 2012 CS (CS1) – Question 50

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple choice

For the shown directed weighted graph, several S-to-T shortest paths exist. Dijkstra updates a vertex’s predecessor only on finding a strictly shorter distance. Which path does it report?

Diagram for GATE 2012 CS (CS1) question 50

SDT
SBDT
SACDT
SACET

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) SACET

Explanation

Distances from S settle B=3, A=4, C=5, E=6 and D=7. C improves E to six, giving predecessor C. E is settled before D and sets T to ten via E→T. D later offers the same T distance ten, which the strict-update rule does not adopt. Thus S→A→C→E→T, D.

More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions

GATE 2013 CS (CS1) Q29 – What is Bellman–Ford’s running time on a complete graph with n vertices?
GATE 2011 CS (CS1) Q64 – An undirected graph has vertices v₁,…,vₙ, n>2. Vertices vᵢ,vⱼ are adjacent iff 0< i−j ≤2;…
GATE 2011 CS (CS1) Q65 – An undirected graph has vertices v₁,…,vₙ, n>2. Vertices vᵢ,vⱼ are adjacent iff 0< i−j ≤2;…
GATE 2010 CS (CS1) Q60 – The undirected graph on vertices 0,…,4 has weight matrix…
GATE 2010 CS (CS1) Q61 – The undirected graph on vertices 0,…,4 has weight matrix…
GATE 2015 CS (CS2) Q47 – Match algorithms 1 Dijkstra shortest path, 2 Floyd–Warshall all-pairs shortest paths, 3…

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →