Question:medium
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\)?
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\)?
Show Hint
A DAG allows shortest paths to be found with one topological sort pass plus one relaxation pass over every edge, with no priority queue needed.
Updated On: Jul 22, 2026
- \(\Theta(m+n)\)
- \(\Theta(m+n\log(n))\)
- \(\Theta(nm)\)
- \(\Theta(n^3)\)
Show Solution
The Correct Option is A
Solution and Explanation
Step 1: See why a DAG is a special, easier case.
In a graph with cycles, we generally cannot compute a vertex's shortest distance until we have looked at all its incoming edges, and a cycle can make that circular. A DAG has no cycles, so we can always order the vertices so that every edge points from an earlier vertex to a later one. That ordering is a topological order.
Step 2: Set up a distance recurrence.
Let $dist[v]$ be the shortest distance from $s$ to $v$. If the vertices are processed in topological order, then when we reach vertex $v$, every predecessor $u$ with an edge $u \to v$ has already had its final $dist[u]$ computed. So we can write
$$ dist[v] = \min_{(u,v)\in E} \big( dist[u] + w(u,v) \big) $$
and this value is guaranteed correct the moment we compute it, because no later vertex can ever feed back into $v$.
Step 3: Count the work for topological sorting.
Getting a topological order, for example with depth first search, touches every vertex once and every edge once, which costs $\Theta(m+n)$.
Step 4: Count the work for filling in the distances.
Going through the vertices in this order and relaxing each outgoing edge exactly once also costs $\Theta(m+n)$ in total, since across the whole run every edge is looked at only once and every vertex is initialized once.
Step 5: Add the two phases together.
$$ \Theta(m+n) + \Theta(m+n) = \Theta(m+n) $$
Step 6: Why the other listed complexities are not the fastest.
$\Theta(m+n\log n)$ belongs to Dijkstra's algorithm with a heap, meant for graphs that are not necessarily acyclic. $\Theta(nm)$ belongs to Bellman Ford, built to tolerate negative edges in graphs with cycles. $\Theta(n^3)$ belongs to Floyd Warshall, solving all pairs at once. All three do more work than the DAG structure requires.
Step 7: State the result.
$$ \boxed{\Theta(m+n)} $$
This is option (A).
In a graph with cycles, we generally cannot compute a vertex's shortest distance until we have looked at all its incoming edges, and a cycle can make that circular. A DAG has no cycles, so we can always order the vertices so that every edge points from an earlier vertex to a later one. That ordering is a topological order.
Step 2: Set up a distance recurrence.
Let $dist[v]$ be the shortest distance from $s$ to $v$. If the vertices are processed in topological order, then when we reach vertex $v$, every predecessor $u$ with an edge $u \to v$ has already had its final $dist[u]$ computed. So we can write
$$ dist[v] = \min_{(u,v)\in E} \big( dist[u] + w(u,v) \big) $$
and this value is guaranteed correct the moment we compute it, because no later vertex can ever feed back into $v$.
Step 3: Count the work for topological sorting.
Getting a topological order, for example with depth first search, touches every vertex once and every edge once, which costs $\Theta(m+n)$.
Step 4: Count the work for filling in the distances.
Going through the vertices in this order and relaxing each outgoing edge exactly once also costs $\Theta(m+n)$ in total, since across the whole run every edge is looked at only once and every vertex is initialized once.
Step 5: Add the two phases together.
$$ \Theta(m+n) + \Theta(m+n) = \Theta(m+n) $$
Step 6: Why the other listed complexities are not the fastest.
$\Theta(m+n\log n)$ belongs to Dijkstra's algorithm with a heap, meant for graphs that are not necessarily acyclic. $\Theta(nm)$ belongs to Bellman Ford, built to tolerate negative edges in graphs with cycles. $\Theta(n^3)$ belongs to Floyd Warshall, solving all pairs at once. All three do more work than the DAG structure requires.
Step 7: State the result.
$$ \boxed{\Theta(m+n)} $$
This is option (A).
Was this answer helpful?
0
Questions Asked in GATE CS exam
A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of \(b\) blocks needs \(\lceil \log_2 b \rceil\) block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.
- GATE CS - 2023
- Database Management Systems