GATE CS 2026 Set 2 Q27 — Shortest Paths (Dijkstra, Bellman-Ford)

The single-source shortest path (SSSP) problem on a weighted Directed Acyclic Graph (DAG) can be solved efficiently using topological sorting in $\Theta(m + n)$ time.

The algorithm proceeds as follows:

1. Topological Sort: Find a topological ordering of the vertices of $G$. This takes $\Theta(m + n)$ time using Depth-First Search (DFS) or Kahn's algorithm.
2. Initialization: Set the distance to the source vertex $s$ as $dist[s] = 0$, and for all other vertices $u \neq s$, set $dist[u] = \infty$. This takes $\Theta(n)$ time.
3. Relaxation: Process each vertex $u$ in the topological order. For each outgoing edge $(u, v)$ with weight $w(u, v)$, update the distance:$$dist[v] = \min(dist[v], dist[u] + w(u, v))$$Since each vertex and edge is processed exactly once, this step takes $\Theta(m + n)$ time.

Therefore, the total worst-case time complexity of the fastest algorithm is $\Theta(m + n)$.

Correct Option: A