Shortest Path in DAGs

Finding shortest paths in a DAG is simpler than Dijkstra. No need for a priority queue or visited set. Process nodes in topological order. For each node $u$, relax all outgoing edges $(u, v)$ by trying to update dp[v] = min(dp[v], dp[u] + w(u,v)).

When you reach node $v$, all possible paths to $v$ have been considered. This runs in $O(V + E)$, faster than Dijkstra's $O((V + E) \log V)$. The topological order guarantees you process nodes in the right sequence.

Space complexity is $O(V)$ for the data structures used.