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: The graph \(G\) is a weighted Directed Acyclic Graph (DAG) with \(m\) edges and \(n\) vertices, and we need the shortest path lengths from source \(s\) to every reachable vertex.
Step 2: Because \(G\) has no cycles, we do not need a general-purpose shortest path algorithm such as Dijkstra's (which needs \(\Theta((m+n)\log n)\) with a Fibonacci heap or \(\Theta(m \log n)\) with a binary heap) or Bellman-Ford (which needs \(\Theta(mn)\)).
Step 3: The fastest known method for shortest paths in a DAG is: (a) compute a topological order of the vertices in \(\Theta(m+n)\) time using DFS or Kahn's algorithm, and (b) process vertices in that topological order, relaxing each outgoing edge exactly once, which takes \(\Theta(m+n)\) time in total.
Step 4: This works because in topological order, by the time we process vertex \(v\), all vertices that can reach \(v\) have already been finalized, so a single relaxation pass correctly computes the shortest distance to every vertex, with no need to revisit any vertex.
Step 5: The total work is therefore \(\Theta(m+n)\) for topological sorting plus \(\Theta(m+n)\) for the relaxation pass, giving an overall worst case time complexity of \(\Theta(m+n)\), which is asymptotically the fastest possible since every edge and vertex must be inspected at least once.
Final Answer: \(\boxed{\Theta(m+n)}\)