Discussion
Let \(G\) be a weighted directed acyclic graph with \(m\) edges and \(n\) vertices. Given \(G\) and a source vertex \(s\) in \(G\), which one of the following options gives the worst case time complexity of the fastest algorithm to find the lengths of shortest paths from \(s\) to all vertices that are reachable from \(s\) in \(G\)?
Answer: A
The fastest algorithm runs in Θ(m + n).
In a directed acyclic graph, single-source shortest paths need no priority queue. Sort the vertices topologically (O(m + n) with depth-first search), then relax the outgoing edges of each vertex in that order. When a vertex is processed, every path into it has already been considered, because all its predecessors come earlier in the order. Each edge is relaxed once, so the total is Θ(m + n), and this works with negative edge weights too.
Θ(m + n log n) is Dijkstra's algorithm with a Fibonacci heap, which ignores the acyclic structure and fails with negative weights. Θ(nm) is Bellman-Ford, for general graphs with negative edges. Θ(n3) is Floyd-Warshall, which computes all pairs.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development