The GATE Grind

GATE 2026 CS (CS2) – Question 37

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

Let $G$ be a weighted directed acyclic graph with $m$ edges and $n$ vertices. Given $G$ and a source vertex $s$, 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$ to all vertices reachable from $s$?

  1. $\Theta(m+n)$
  2. $\Theta(m+n\log n)$
  3. $\Theta(nm)$
  4. $\Theta(n^3)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $\Theta(m+n)$

Explanation

In a weighted DAG, shortest paths from a source can be found by processing the vertices in topological order and relaxing each outgoing edge once. Computing a topological order and relaxing all edges together take $\Theta(m+n)$ time. Therefore, option (A) is correct.