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

  1. A.

    Θ(m+n)

  2. B.

    Θ(m+nlog⁡n)

  3. C.

    Θ(nm)

  4. D.

    Θ(n3)

Attempted by 339 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…