Which of the following algorithm can be used to efficiently calculate single source shortest paths in a Directed Acyclic Graph?
(A) Dijkstra
(B) Bellman-Ford
(C) Topological Sort
(D) Strongly Connected Component
Answer: (C)
Explanation: Using Topological Sort, we can find single source shortest paths in O(V+E) time which is the most efficient algorithm. See following for details.
Shortest Path in Directed Acyclic Graph
Quiz of this Question
Whether you’re preparing for your first job interview or aiming to upskill in this ever-evolving tech landscape, neveropen Courses are your key to success. We provide top-quality content at affordable prices, all geared towards accelerating your growth in a time-bound manner. Join the millions we’ve already empowered, and we’re here to do the same for you. Don’t miss out – check it out now!