Longest path in a Directed Acyclic Graph

The problem, simply

You get a directed graph with no loops (a DAG). Each arrow has a weight, which can be negative. You also get a start stop src.

For every stop, find the largest total weight of any path from src to it. A stop you cannot reach gets minus infinity.

In a graph with loops this problem is extremely hard. Because the arrows never loop back, it becomes easy, and that is the whole point of the question.

A story to remember it

Picture it

Examples

Way 1: the simple way

Walk every path. From the start, follow each arrow, then each arrow from there, and so on, carrying the points so far. Every time you reach a stop, keep the biggest score seen. No loops exist, so the walk always ends.

import java.util.*;

class Solution {
    static final int NEG = Integer.MIN_VALUE;

    public int[] longestPath(int V, int[][] edges, int src) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(new int[]{e[1], e[2]});
        int[] best = new int[V];
        Arrays.fill(best, NEG);
        walk(adj, src, 0, best);
        return best;
    }

    private void walk(List<List<int[]>> adj, int u, int points, int[] best) {
        best[u] = Math.max(best[u], points);
        for (int[] e : adj.get(u)) walk(adj, e[0], points + e[1], best);   // every path, again and again
    }
}

How long it takes: the number of paths can double with every stop (picture a ladder where each rung offers two arrows), so O(2^V). Extra room: the recursion, O(V).

Way 2: the clever way

Do the slide park trick.

1. Put the stops in topological order: every arrow points from an earlier stop to a later one. Use Kahn's method (or depth first search).
2. Set best[src] = 0 and every other best to minus infinity.
3. Go through the stops in that order. If best[u] is minus infinity, skip it. Otherwise, for each arrow u > v with weight w, set best[v] = max(best[v], best[u] + w).

When we reach u, every arrow into u comes from a stop we already handled, so best[u] is already final. This is shortest path on a DAG with min turned into max.

import java.util.*;

class Solution {
    static final int NEG = Integer.MIN_VALUE;

    public int[] longestPath(int V, int[][] edges, int src) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        int[] in = new int[V];
        for (int[] e : edges) {
            adj.get(e[0]).add(new int[]{e[1], e[2]});
            in[e[1]]++;
        }
        // 1. topological order with Kahn's method
        Queue<Integer> ready = new ArrayDeque<>();
        for (int i = 0; i < V; i++) if (in[i] == 0) ready.add(i);
        List<Integer> order = new ArrayList<>();
        while (!ready.isEmpty()) {
            int u = ready.poll();
            order.add(u);
            for (int[] e : adj.get(u)) if (--in[e[0]] == 0) ready.add(e[0]);
        }
        // 2. push the best scores forward in that order
        int[] best = new int[V];
        Arrays.fill(best, NEG);
        best[src] = 0;
        for (int u : order) {
            if (best[u] == NEG) continue;              // not reachable from src
            for (int[] e : adj.get(u)) {
                best[e[0]] = Math.max(best[e[0]], best[u] + e[1]);
            }
        }
        return best;
    }
}

How long it takes: the topological order is O(V + E), and the second pass looks at every arrow once, O(V + E). Extra room: the neighbour lists, counts and order, O(V + E).

Watch out for

• Processing stops in number order instead of topological order. A stop may get a better score after you already pushed its old score forward.
• Trying Dijkstra with max. It fails: Dijkstra relies on scores only getting worse along a path, which is not true here.
• Negating all weights and running a shortest path method works on a DAG too, but do it with the topological order, not Dijkstra (negated weights are negative).
• If the graph might have a loop, the topological order will be shorter than V. Check it.

What interviewers ask next

• Why is longest path hard in a general graph? With loops allowed, a longest simple path that visits every stop would solve the Hamiltonian path problem, which is NP hard. No loops removes that difficulty.
• How do you print the route? Store parent[v] = u whenever best[v] improves, then walk back from the stop.
• Longest path anywhere in the DAG, not from one start? Start every stop at 0 instead of minus infinity, run the same pass, and take the largest value.
• Where does this show up? Project planning (the critical path: the longest chain of tasks decides the finish time), longest increasing subsequence, and course scheduling with durations.
• Can you do it with recursion and memory? Yes: best(u) = max over arrows u > v of w + best(v), with a memo table. Each stop is solved once, O(V + E).

Remember this

Grown-up words: stops are vertices, slides are directed weighted edges, a graph with no loops is a DAG, lining up the stops is a topological sort, pushing scores forward is relaxation, minus infinity marks an unreachable vertex, and the longest route is the longest path, the critical path in project planning.