Shortest Path Algorithm

Here is the algorithm for shortest path in a DAG:

$1.$ Compute topological order

$2.$ Initialize dp[source] = 0, all others to $\infty$

$3.$ For each node $u$ in topological order: For each edge $(u, v)$: dp[v] = min(dp[v], dp[u] + w(u,v))

$4.$ Output dp[destination]

Here is why this works. When you process node $u$, all nodes that can reach $u$ have already updated it. So dp[u] is finalized and you can safely use it to update neighbors.

This runs in $O(V + E)$ time and uses $O(V)$ space.