Let 𝐺 be a weighted directed acyclic graph with 𝑚 edges and 𝑛 vertices.…
PYQ GATE 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 339 students.
Sign up free to check your answer
Sign up freeLoading lesson…

