Implement the solution to the Longest Path in a Directed Acyclic Graph (DAG) problem using dynamic programming.?

The Longest Path in a Directed Acyclic Graph problem asks us to find the longest simple path in a directed acyclic graph. A simple path is a path with no repeated vertices.

One approach to solve this problem is to use dynamic programming. We can define an array ‘dp‘ where ‘dp[i]‘ represents the length of the longest path starting from vertex ‘i‘. We can then iterate over every vertex in the graph and compute ‘dp[i]‘ using the following recurrence relation:

dp[i] = max(dp[j] + 1) for every edge (i, j) in the graph

Here, we add 1 to the longest path starting from vertex ‘j‘ and going through edge ‘(i, j)‘ to get the longest path starting from vertex ‘i‘.

Once we have computed ‘dp[i]‘ for every vertex ‘i‘, the answer will be the maximum value in the ‘dp‘ array.

Here is the Java code to implement this solution:

import java.util.*;

public class LongestPathDAG {
    static List<Integer>[] adj;
    static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // number of vertices
        int m = sc.nextInt(); // number of edges
        adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            adj[a].add(b);
        }
        int ans = longestPath();
        System.out.println(ans);
    }

    static int longestPath() {
        int[] dp = new int[n];
        Arrays.fill(dp, -1);
        for (int i = 0; i < n; i++) {
            if (dp[i] == -1) {
                dfs(i, dp);
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    static void dfs(int u, int[] dp) {
        dp[u] = 0;
        for (int v : adj[u]) {
            if (dp[v] == -1) {
                dfs(v, dp);
            }
            dp[u] = Math.max(dp[u], dp[v] + 1);
        }
    }
}

The ‘longestPath‘ function computes the ‘dp‘ array using the recurrence relation described above. It also calls the ‘dfs‘ function to do a depth-first search of the graph and ensure that every vertex is visited.

The ‘dfs‘ function updates the ‘dp‘ array for vertex ‘u‘ by iterating over all its neighbors ‘v‘. If we haven’t computed the longest path starting from ‘v‘, we first call ‘dfs(v, dp)‘. We then update ‘dp[u]‘ by taking the maximum of its current value and the longest path starting from ‘v‘ plus 1.

The main function reads in the input graph (in the form of a list of directed edges) and calls ‘longestPath‘ to compute the answer. It then prints the answer to the console.