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+nlogโกn)
- C.
ฮ(nm)
- D.
ฮ(n3)
Attempted by 313 students.
Sign up free to check your answer
Sign up freeLoading lessonโฆ