Let 𝐺 be a weighted directed acyclic graph with 𝑚 edges and 𝑛 vertices.…
2026
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.
Θ(m+n)
- B.
Θ(m+nlogn)
- C.
Θ(nm)
- D.
Θ(n3)
Attempted by 68 students.
Show answer & explanation
Correct answer: A
Shortest Path in Directed Acyclic Graph
For a weighted Directed Acyclic Graph (DAG), the shortest paths from a single source can be found efficiently using a combination of topological sorting and edge relaxation.
Algorithm Steps
Compute the topological sort of the graph vertices.
Initialize distances from the source to infinity, except source distance is zero.
Process vertices in topological order and relax all outgoing edges.
Time Complexity Analysis
Topological sorting takes O(V + E) time. Relaxing all edges also takes O(V + E) time. Therefore, the total worst-case time complexity is O(V + E), which is linear.