Course4all
Join us on telegram
Home/dsa/Graphs/Longest Path in a DAG

Longest Path in a DAG

Master this topic with zero to advance depth.

Longest Path in a DAG

Given a Directed Acyclic Graph (DAG) and a source vertex src, find the distance to the farthest vertex from src.

In a general graph, finding the longest path is NP-hard. However, in a DAG, it can be solved in linear time using Topological Sort.

Visual Representation

Nodes: 0 to 5 Edges: (0,1,5), (0,2,3), (1,3,6), (1,2,2), (2,4,4), (2,5,2), (2,3,7), (3,4,-1), (4,5,-2) Topological Order: 0, 1, 2, 3, 4, 5 Relax edges in this order to find max distances.
Hard

Examples

Input: n=6, src=1, edges=[[0,1,5],[0,2,3],[1,3,6],[1,2,2],[2,4,4],[2,5,2],[2,3,7],[3,4,-1],[4,5,-2]]
Output: [inf, 0, 2, 9, 8, 6]

Distances from node 1: to 3 is 9 (1->2->3 is 2+7), to 4 is 8, etc.

Approach 1

Level I: Brute Force (Recursion + Memoization)

Intuition

The longest path from a node u is max(weight(u, v) + longestPath(v)) for all neighbors v. Since the graph is a DAG, we can use memoization to avoid redundant computations.

Thought Process

  1. Define dfs(u) as the longest path starting from node u.
  2. In dfs(u):
    • If u is already in memo, return memo[u].
    • Initialize max_dist = 0 (or some base case).
    • For each neighbor v with weight w:
      • max_dist = max(max_dist, w + dfs(v)).
    • Store and return max_dist.

Complexity

  • Time: O(V+E)O(V + E)
  • Space: O(V)O(V)
⏱ O(V + E)💾 O(V)

Detailed Dry Run

src=1. Edges from 1: (3,6), (2,2).

  • dfs(3): edge (4,-1). dfs(4): edge (5,-2). dfs(5): 0.
  • dfs(4) = -1 + 0 = -1.
  • dfs(3) = -1 + -1 = -2. (Wait, let's say base case is 0 for sink).
  • dfs(1) = max(6 + dfs(3), 2 + dfs(2))...
java
class Solution {
    public int[] longestPath(int n, int src, List<Edge>[] adj) {
        Integer[] memo = new Integer[n];
        int[] res = new int[n];
        for (int i = 0; i < n; i++) res[i] = dfs(i, adj, memo);
        return res; // Distance from each node to sink
    }
    private int dfs(int u, List<Edge>[] adj, Integer[] memo) {
        if (memo[u] != null) return memo[u];
        int maxDist = 0;
        for (Edge e : adj[u]) maxDist = Math.max(maxDist, e.w + dfs(e.v, adj, memo));
        return memo[u] = maxDist;
    }
}
Approach 2

Level III: Optimal (Topological Sort + Relaxation)

Intuition

Processing nodes in topological order allows finding the longest path in O(V+E)O(V+E).

Pattern: DAG Relaxation

⏱ O(V + E)💾 O(V + E)

Detailed Dry Run

Order: 0,1,2,3,4,5. Relax edges from 1. 1->2->3 is longer than 1->3 directly.

java
class Solution {
    public int[] longestPath(int n, int src, List<int[]>[] adj) {
        Stack<Integer> s = new Stack<>(); boolean[] vis = new boolean[n];
        for (int i=0; i<n; i++) if (!vis[i]) topo(i, vis, s, adj);
        int[] dist = new int[n]; Arrays.fill(dist, -1000000); dist[src] = 0;
        while (!s.isEmpty()) {
            int u = s.pop();
            if (dist[u] != -1000000) {
                for (int[] e : adj[u]) if (dist[e[0]] < dist[u] + e[1]) dist[e[0]] = dist[u] + e[1];
            }
        }
        return dist;
    }
    private void topo(int u, boolean[] vis, Stack<Integer> s, List<int[]>[] adj) {
        vis[u] = true; for (int[] e : adj[u]) if (!vis[e[0]]) topo(e[0], vis, s, adj);
        s.push(u);
    }
}
← Previous QuestionCritical Connections in a Network
Next Question →Reconstruct Itinerary