GATE 2026 CS (CS2) – Question 37
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$?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) $\Theta(m+n)$
Explanation
**1. Use acyclicity.** A DAG has a topological order in which every directed edge goes from an earlier vertex to a later one. This order can be found by DFS or an indegree-based traversal in O(n+m) time.
**2. Relax once in that order.** Initialize d(s) = 0 and other distances to infinity. When a reachable vertex is processed, all paths into it come from already processed vertices, so its distance is final. Relax each outgoing edge once. Negative weights are allowed because there are no cycles.
**3. Count work.** Initialization/order processing costs O(n); edge processing costs O(m). Thus the worst-case running time is **Θ(n+m), A**. A priority queue is unnecessary; it would add work without exploiting the DAG structure.
More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions
- GATE 2025 CS (CS1) Q18
- GATE 2025 CS (CS1) Q43
- GATE 2025 CS (CS1) Q64
- GATE 2025 CS (CS2) Q29
- GATE 2025 CS (CS2) Q37
- GATE 2025 CS (CS2) Q59
All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →