Longest Path in DAGs

Longest path is NP-hard on general graphs.

But on DAGs, you solve it by flipping the shortest path algorithm. Define dp[u] as the longest distance from the source to $u$. Initialize dp[source] = 0 and dp[u] = -Infinity for all other nodes. For each node $u$ in topological order, relax with maximization: dp[v] = max(dp[v], dp[u] + w). The logic is identical to shortest path, with $\max$ instead of $\min$.