GATE CS 2026 Set 2 Q.37: Single-Source and All-Pairs Shortest Paths

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

$\Theta(m + n)$

$\Theta(m + n \log(n))$

$\Theta(nm)$

$\Theta(n^3)$

Official answer and solution

Official answer: A
From: Official GATE 2026 answer key

Solution

Use topological sorting followed by single-pass edge relaxation on a DAG.

Because $G$ is a Directed Acyclic Graph (DAG), we can topologically sort the vertices in $\Theta(m + n)$ time and then relax the outgoing edges of each vertex in topological order in $\Theta(m + n)$ total time. Thus single-source shortest paths on a DAG takes $\Theta(m + n)$ time in the worst case.

Final answer

Option (A)

Common trap

Choosing Dijkstra's complexity $\Theta(m + n \log n)$ or Bellman-Ford $\Theta(nm)$ when $G$ is a DAG.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 2 (CS2)
Question: 37 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source