Question

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\)?

• A. \(\Theta(m+n)\)
• B. \(\Theta(m+n\log(n))\)
• C. \(\Theta(nm)\)
• D. \(\Theta(n^3)\)

Hint:

A DAG allows shortest paths to be found with one topological sort pass plus one relaxation pass over every edge, with no priority queue needed.

Answer 1

The Correct Option is A

Step 1: Recall the standard algorithm for shortest paths in a DAG.
Since \(G\) has no cycles, shortest paths from a single source can be found using topological sorting followed by one pass of edge relaxation, instead of a general shortest path algorithm like Dijkstra or Bellman Ford.

Step 2: Break down the algorithm's steps.
First, compute a topological order of the vertices. This takes
\[ \Theta(m+n) \]
using depth first search, because every vertex and every edge is visited exactly once.
Second, initialize the distance to \(s\) as \(0\) and every other reachable vertex as infinity, which takes
\[ \Theta(n) \]
Third, process the vertices in topological order, and for each vertex, relax every outgoing edge once. Since each edge is relaxed exactly once across the whole algorithm, this step also takes
\[ \Theta(m) \]

Step 3: Add up the total time.
Combining all three parts:
\[ \Theta(m+n)+\Theta(n)+\Theta(m)=\Theta(m+n) \]

Step 4: Explain why this works correctly even with negative edge weights.
Because \(G\) is acyclic, processing vertices in topological order guarantees that by the time a vertex \(v\) is processed, every edge that could possibly improve the distance to \(v\) has already been relaxed. So this simple linear pass always finds the correct shortest distances, and there is no need for the extra machinery, such as a priority queue, that general graphs require.

Step 5: Compare with the other options.

(B) \(\Theta(m+n\log(n))\): This is the time complexity of Dijkstra's algorithm using a binary heap, which applies to general graphs with nonnegative weights. It is slower than what the DAG structure allows, and it is not needed here. Incorrect for this setting.

(C) \(\Theta(nm)\): This matches algorithms like Bellman Ford, which handle general graphs that may contain negative weight edges but no negative cycles. It is far more work than necessary for a DAG. Incorrect.

(D) \(\Theta(n^3)\): This is the complexity of all pairs shortest path algorithms such as Floyd Warshall, which solve a much bigger problem, every pair of vertices instead of just a single source. Incorrect and unnecessarily slow here.

Step 6: Final conclusion.
The fastest algorithm for single source shortest paths in a DAG runs in
\[ \boxed{\Theta(m+n)} \]
Hence, the correct option is (A).