Question

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 𝐺?

• A. Θ(𝑚+ 𝑛)
• B. Θ(𝑚+ 𝑛log(𝑛))
• C. Θ(𝑛𝑚)
• D. \(\Theta(n^3)\)

Hint:

Since the graph is a DAG, topologically sort the vertices in \(\Theta(m+n)\) time, then relax edges once in topological order. Total cost is \(\Theta(m+n)\), faster than Dijkstra or Bellman-Ford.

Answer 1

The Correct Option is A

Step 1: Since \(G\) is acyclic, there always exists a linear (topological) ordering of vertices such that every edge goes from an earlier vertex to a later one.
Step 2: Using DFS-based topological sorting, we can order all \(n\) vertices in \(\Theta(m+n)\) time, visiting each vertex and edge once.
Step 3: Once ordered, initialize \(dist[s]=0\) and \(dist[v]=\infty\) for all other vertices, then scan vertices in topological order, and for each vertex, relax all of its outgoing edges. Because a vertex is only relaxed after all its predecessors in the DAG have already been finalized, one pass suffices to get the exact shortest distances -- no repeated relaxations like in Bellman-Ford are needed.
Step 4: This single relaxation sweep touches each of the \(m\) edges exactly once, contributing another \(\Theta(m+n)\) term.
Step 5: Adding the topological sort cost and the relaxation cost gives a combined worst case running time of \(\Theta(m+n)\), beating general graph algorithms like Dijkstra's \(\Theta(m \log n)\) or Bellman-Ford's \(\Theta(mn)\), both of which ignore the acyclic structure.
Final Answer: \(\Theta(m+n)\)