The GATE Grind

GATE 2015 CS (CS2) – Question 47

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

Match algorithms 1 Dijkstra shortest path, 2 Floyd–Warshall all-pairs shortest paths, 3 binary search, 4 backtracking graph search, with paradigms i divide and conquer, ii dynamic programming, iii greedy, iv depth-first search, v breadth-first search.

  1. 1–i,2–iii,3–i,4–v
  2. 1–iii,2–iii,3–i,4–v
  3. 1–iii,2–ii,3–i,4–iv
  4. 1–iii,2–ii,3–i,4–v

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) 1–iii,2–ii,3–i,4–iv

Explanation

Dijkstra greedily finalizes the nearest unsettled vertex, 1–iii. Floyd–Warshall builds shortest paths through successively allowed intermediate vertices, 2–ii. Binary search halves the search interval, 3–i. Backtracking explores a branch then retreats, following depth-first search, 4–iv. Thus C.

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

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