Let be a weighted directed acyclic graph with edges and vertices. Given and a source vertex in , which one of the following options gives the worst case time complexity of the fastest algorithm to find the lengths of shortest paths from to all vertices that are reachable from in ?
ANSWER
The worst-case time complexity of the fastest algorithm to find shortest path lengths from source s to all reachable vertices in a weighted DAG is Θ(m+n), given by option (A).
Official answer: ASource: Official answer key, GATE 2026 CS2 (IIT Guwahati)
G is a weighted directed acyclic graph (DAG), so a topological ordering of its n vertices always exists and can be computed in Θ(m+n) time using DFS with post-order reversal, or Kahn's algorithm (repeatedly removing in-degree-0 vertices).
Initialize dist[s] = 0 and dist[v] = ∞ for every other vertex v.
Process the vertices in topological order. When a vertex u is dequeued, dist[u] is already finalized to its true shortest-path length, because every edge into u comes from a vertex earlier in the topological order, and all such vertices have already been processed and relaxed.
For each vertex u processed, relax every outgoing edge (u, v): if dist[u] + w(u, v) < dist[v], set dist[v] = dist[u] + w(u, v).
Each of the n vertices is processed exactly once, and each of the m edges is relaxed exactly once (when its tail vertex is processed) — there is no repeated relaxation, unlike in Bellman-Ford. So the relaxation phase costs Θ(n) (vertex visits) + Θ(m) (edge relaxations) = Θ(m+n).
Adding the Θ(m+n) cost of computing the topological order gives a total worst-case running time of Θ(m+n) + Θ(m+n) = Θ(m+n).
This is asymptotically optimal: any algorithm must read the entire input graph (all m edges and n vertices), which already takes Ω(m+n) time, so no algorithm can beat Θ(m+n) in the worst case.
Comparing with the other options confirms why they are wrong here: Θ(m + n log n) (B) is Dijkstra's complexity with a binary heap, needed only for general graphs with non-negative weights (no topological order available); Θ(nm) (C) is Bellman-Ford's complexity, needed for general graphs that may contain cycles; Θ(n^3) (D) is the complexity of all-pairs algorithms like Floyd-Warshall, which solve a different (harder) problem. Since G is guaranteed acyclic, the topological-order relaxation method is strictly faster than all of these, giving Θ(m+n) as the correct worst-case complexity of the fastest algorithm.
Therefore the correct option is (A) Θ(m+n).
KEY IDEA
For a weighted DAG, computing a topological order (Θ(m+n) via DFS or Kahn's algorithm) and then relaxing edges in that order gives correct single-source shortest paths in one linear pass — no priority queue or repeated relaxation is needed, unlike in general graphs.
WATCH OUT FOR
Assuming the graph is a general weighted graph (with cycles/negative or arbitrary edges) and reaching for Dijkstra's Θ(m + n log n) (option B) or Bellman-Ford's Θ(nm) (option C), forgetting that acyclicity permits a much faster topological-order relaxation algorithm.
From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 28 Graph algorithms questions, with notes
