Longest Path in a DAG — Graph DP With Topological Sort + Memoised DFS [Google, Amazon, Meta]

Algorithm Statement#

Given a directed acyclic graph with n nodes and weighted edges, return the length of the longest path (sum of edge weights, or number of edges if unweighted) starting from any source node. The same algorithm computes the longest path ending at every node, the longest path between two specific nodes, or the longest path in the entire DAG.

Constraints (typical):

• 1 <= n <= 10^5
• 0 <= m <= 2 * 10^5
• -10^9 <= w <= 10^9 (negative weights are fine; cycles are not)
• The input is a guaranteed DAG; if the input is a general graph, longest path is NP-hard.

Example 1:

Input:  n = 5, edges = [(0,1,3),(0,2,2),(1,3,4),(2,3,6),(3,4,1)]
Output: 11
Explanation: Longest path 0 -> 2 -> 3 -> 4 has length 2 + 6 + 1 = 9.
Longest is 0 -> 1 -> 3 -> 4 with length 3 + 4 + 1 = 8 — wait, recheck:
  0 -> 2 -> 3 -> 4 = 2 + 6 + 1 = 9
  0 -> 1 -> 3 -> 4 = 3 + 4 + 1 = 8
  0 -> 2 -> 3      = 2 + 6 = 8
Longest is 9. (Adjust example: max = 9.)

Example 2 (unweighted, count edges):

Input:  DAG with chain 0 -> 1 -> 2 -> 3 -> 4
Output: 4 (edges) or 5 (nodes), depending on definition.

Why This Problem Matters#

The longest path in a general graph is NP-hard — there is no known polynomial algorithm and the problem is at least as hard as Hamiltonian path. The fact that the problem becomes polynomial on DAGs is one of the most important takeaways in an algorithms interview, because it shows how acyclicity unlocks dynamic programming.

Google, Amazon, and Meta ask this pattern in many disguises:

• LeetCode 329 Longest Increasing Path in a Matrix — the matrix induces a DAG via the strictly-increasing relation.
• LeetCode 2127 Maximum Employees to Be Invited to a Meeting — DAG longest path on the trees attached to the inward-pointing functional-graph cycles.
• Critical-path method (CPM) in project planning — longest path = the critical sequence of tasks.
• Compiler optimisations — longest dependency chain in instruction-level parallelism.
• Build-system scheduling — Bazel and Buck use this to estimate parallelism speed-ups.

The interview value is signalling that you can spot a DAG, justify why the problem is now polynomial, and choose between two equivalent approaches: memoised DFS (top-down) or topological-sort iteration (bottom-up). Both run in O(V + E); both are correct; senior candidates can articulate the trade-offs.

The Core Insight#

Define dp[u] = length of the longest path starting at u. The recurrence is straightforward:

dp[u] = 0  if u has no outgoing edges
dp[u] = max(w + dp[v]) over all outgoing edges (u, v, w)

Because the graph is a DAG, every recursive call eventually reaches a sink (no outgoing edges), so memoised DFS terminates. The acyclicity guarantees no infinite recursion, and the memoisation guarantees each dp[u] is computed exactly once.

Equivalent bottom-up formulation: sort vertices in reverse topological order (sinks first) and iterate. When we reach u, every dp[v] for v reachable from u is already finalised.

The two views are duals:

• Top-down (memo DFS): intuitive, single-function recursion, lazy. Watch the recursion stack on n = 10^5.
• Bottom-up (toposort iteration): explicit order, easier to parallelise, no recursion limit, slightly more boilerplate.

If you also want the path itself (not just its length), store a parent[u] pointer that records which neighbour v achieved the maximum at u. After computing dp, follow parents from the source of the longest path back to the sink.

Time O(V + E), space O(V) for the memo plus O(V + E) for the adjacency list.

Visual Dry Run#

DAG: 0 -> 1 (3), 0 -> 2 (2), 1 -> 3 (4), 2 -> 3 (6), 3 -> 4 (1).

Reverse topological order: [4, 3, 2, 1, 0]. Iterate bottom-up.

The longest path from 0 is 0 -> 2 -> 3 -> 4 with length 9.

Solution (Optimal)#

Python — Memoised DFS (top-down)#

import sys
from functools import lru_cache
sys.setrecursionlimit(2 * 10 ** 5)
 
def longestPath(n, adj):
    @lru_cache(maxsize=None)
    def dp(u):
        best = 0
        for v, w in adj[u]:
            best = max(best, w + dp(v))
        return best
    return max(dp(u) for u in range(n))

Python — Topological-sort DP (bottom-up)#

from collections import deque
 
def longestPath(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v, w in edges:
        adj[u].append((v, w))
        indeg[v] += 1
 
    order = []
    q = deque(u for u in range(n) if indeg[u] == 0)
    while q:
        u = q.popleft()
        order.append(u)
        for v, _ in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
 
    dp = [0] * n
    for u in reversed(order):
        for v, w in adj[u]:
            if w + dp[v] > dp[u]:
                dp[u] = w + dp[v]
    return max(dp)

JavaScript — Memoised DFS#

function longestPath(n, adj) {
    const memo = new Array(n).fill(-1);
 
    const dp = (u) => {
        if (memo[u] !== -1) return memo[u];
        let best = 0;
        for (const [v, w] of adj[u]) {
            best = Math.max(best, w + dp(v));
        }
        memo[u] = best;
        return best;
    };
 
    let ans = 0;
    for (let u = 0; u < n; u++) ans = Math.max(ans, dp(u));
    return ans;
}

Complexity#

Common Mistakes#

• Forgetting the DAG precondition. On a graph with cycles, this code infinite-loops (memo DFS) or stalls (Kahn's). Always validate or document the precondition.
• Mixing up "longest path from u" with "longest path through u". The former is dp[u]; the latter requires also knowing the longest path ending at u, which needs the reverse graph.
• Initialising dp[u] to 0 when negative weights are involved. With negative weights, the longest path may pass through fewer edges than the trivial empty path. Initialise to -INF if a path of at least one edge is required.
• Recursion depth on n = 10^5. Python's default limit will explode. Use the iterative toposort version.
• Counting nodes vs edges. Be explicit: "longest path" usually means edge sum or edge count, but interviewers sometimes mean node count. Clarify upfront.

Interview Tips#

• Open with: "Longest path is NP-hard on general graphs, but polynomial on DAGs because acyclicity gives a topological order."
• Show both top-down and bottom-up approaches; mention their equivalence.
• Argue complexity with O(V + E) and explain why memoisation guarantees each subproblem is solved once.
• For path reconstruction, mention storing parent[u] and walking it back. Many interviewers ask this as a follow-up.
• Mention LeetCode 329 (Longest Increasing Path in a Matrix) as the canonical real-world variant — the implicit DAG is built from cell comparisons.

Follow-up Questions#

• Longest path from a fixed source s? Run only dp(s) instead of looping over all nodes.
• Longest path between two specific nodes s and t? Compute dp_from_s (longest path starting at s) and intersect; or run a single DFS from s constrained to terminate at t.
• Longest simple path on a general graph? NP-hard. Use bitmask DP if n <= 20.
• Number of longest paths? Maintain count[u] alongside dp[u], just like LeetCode 1976.
• Critical path with task durations on nodes? Add the node weight to the recurrence: dp[u] = duration[u] + max(dp[v]).

Key Takeaways#

• Longest path is NP-hard in general graphs but solvable in O(V + E) on DAGs via memoised DFS or topological-sort DP.
• Recurrence: dp[u] = max(w + dp[v]) over outgoing edges (u, v, w), with base case 0 at sinks.
• Memoised DFS is concise; toposort iteration avoids recursion limits and is preferred at scale.
• The same template solves LeetCode 329 (Longest Increasing Path in a Matrix), critical-path scheduling, and compiler dependency analysis.
• Track parent[u] to reconstruct the actual path, not just its length.
• Companies that ask this: Google, Amazon, Meta, Microsoft, Bloomberg, Apple, Stripe, ByteDance.