Correct : a

The correct answer is Option A — Θ(m + n).
For a weighted directed acyclic graph (DAG), the fastest shortest path algorithm exploits the fact that a DAG has no cycles, allowing a topological sort-based approach that is more efficient than both Dijkstra and Bellman-Ford.
Algorithm:
Topological Sort: Compute a topological ordering of all vertices in G using DFS. This takes Θ(m + n) time.
Relax edges in topological order: Initialize dist[s] = 0 and dist[v] = ∞ for all other vertices. Process each vertex u in topological order — for every outgoing edge (u, v) with weight w, update dist[v] = min(dist[v], dist[u] + w). Each edge is relaxed exactly once → Θ(m + n) total.
Total: Θ(m + n).
Why the other options are incorrect:
Option B — Θ(m + n log n): This is the complexity of Dijkstra''s algorithm using a binary heap. Dijkstra requires a priority queue and cannot handle negative weights, making it suboptimal for a DAG. Incorrect.
Option C — Θ(nm): This is Bellman-Ford's complexity, which is needed for general graphs with negative edges but is far too slow for a DAG. Incorrect.
Option D — Θ(n²): This corresponds to Dijkstra using an adjacency matrix, which is even slower. Incorrect.
The key advantage of the DAG algorithm is that it works correctly even with negative edge weights (since there are no negative cycles in a DAG), while achieving the optimal linear time complexity.