Longest Path in a Directed Acyclic Graph

Problem Overview

Longest paths are NP-hard on general graphs, but a DAG has a topological order.

Intuition

Longest paths are NP-hard on general graphs, but a DAG has a topological order. Process vertices in that order and relax each outgoing edge by maximizing distance - the same idea as shortest paths on a DAG, with max instead of min. Unreachable nodes stay at INT_MIN (shown as INF by the driver).

Algorithm

1Build an adjacency list of (neighbor, weight) and in-degrees from edges.
2Kahn topological sort: queue all in-degree 0 nodes, peel edges, record order.
3dist[i] = INT_MIN for all i; dist[src] = 0.
4For each u in topo order with dist[u] reachable: for each edge u -> v with weight w, set dist[v] = max(dist[v], dist[u] + w).
5Return dist.

Example Walkthrough

Input: V = 5, src = 1, edges = [[0,1,1],[0,2,2],[1,4,4],[3,2,-1],[4,2,3],[4,3,6]]

1. dist starts as [INF, 0, INF, INF, INF].
2. From 1 relax 1->4: dist[4]=4. From 4: dist[2]=7, dist[3]=10.
3. From 3 relax 3->2: dist[2]=max(7, 10+(-1))=9. Vertex 0 stays INF.

Output: [INF, 0, 9, 10, 4]

Common Pitfalls

• Do not run Dijkstra for longest paths - it assumes minimizing and positive weights.
• Only relax from nodes with a finite dist; otherwise you invent paths from nowhere.
• INT_MIN is the unreachable sentinel - the platform prints it as INF.
• Negative edge weights are fine on a DAG with this topo + relax method.

Longest Path in a Directed Acyclic Graph.java

Java

// Approach: Longest paths in a DAG = topo order, then relax edges maximizing
// distance. Kahn topo, init dist[src]=0 and others to INT_MIN (unreachable /
// INF in the driver). Skip nodes still at INT_MIN so we never extend from an
// unreachable vertex.
// Complexity: O(V + E) time and O(V + E) space.

import java.util.*;

class Solution {

    public int[] maxDistance(int V, int src, ArrayList<ArrayList<Integer>> edges) {
        ArrayList<ArrayList<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }

        int[] inDegree = new int[V];
        for (ArrayList<Integer> edge : edges) {
            int u = edge.get(0);
            int v = edge.get(1);
            int w = edge.get(2);
            adj.get(u).add(new int[]{v, w});
            inDegree[v]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < V; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        List<Integer> topoOrder = new ArrayList<>();
        while (!queue.isEmpty()) {
            int u = queue.poll();
            topoOrder.add(u);

            for (int[] neighbor : adj.get(u)) {
                int v = neighbor[0];
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.add(v);
                }
            }
        }

        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MIN_VALUE);
        dist[src] = 0;

        for (int u : topoOrder) {
            if (dist[u] != Integer.MIN_VALUE) {
                for (int[] neighbor : adj.get(u)) {
                    int v = neighbor[0];
                    int weight = neighbor[1];
                    if (dist[u] + weight > dist[v]) {
                        dist[v] = dist[u] + weight;
                    }
                }
            }
        }

        return dist;
    }
}

Was this solution helpful?