Course contentsShow
← Computer Science
Lesson 950 of 2,87222. Dynamic ProgrammingFree lesson

DP on DAGs: Longest Path

Computing longest paths in directed acyclic graphs using topological order and dynamic programming.

DP on DAGs: Longest Path

What You'll Learn

You'll learn how to find the longest path in a directed acyclic graph (DAG) by combining topological sorting with dynamic programming.

The Core Problem

In most graphs, finding the longest path is extremely difficult (NP-hard). But DAGs are special—their acyclic structure lets us use DP efficiently!

The key insight: process nodes in topological order. This guarantees that when you compute a node's longest path, all paths leading to it have already been computed.

How It Works

Think of a DAG like courses with prerequisites. You can't take Advanced Algorithms before Data Structures. The topological order ensures you always process prerequisites first.

The Algorithm

  1. Compute topological order of the DAG
  2. Initialize: Set distance to starting node as 0, all others as negative infinity
  3. Process in topological order: For each node u:
    • For each outgoing edge u → v with weight w:
    • Update dist[v] = max(dist[v], dist[u] + w)
  4. Result: Maximum value in dist[] is the longest path length

Why Topological Order Matters

Since you process nodes in dependency order, when you reach node v, all possible paths ending at v have already been considered. This prevents cycles from breaking the computation and ensures each subproblem is solved exactly once.

Time Complexity

O(V + E) — you visit each vertex and edge once during topological sort and DP update.

Analogy

Imagine climbing a mountain with checkpoints. You can only reach higher checkpoints from lower ones. At each checkpoint, you record the longest trail taken so far. By the summit, you know the longest possible route.

Key Takeaway: Longest path in a DAG is efficiently solvable using DP over topological order, leveraging the acyclic structure to ensure subproblems are resolved before they're needed.