PK

PKBytes

Explore tracks
Chapter 37: Graph Dynamic Programming and DAG Applications
37.03Intermediate / Advanced3 topics13 min2 interactive animations

Longest paths

The longest path is easy on a DAG and hard in general graphs; the DAG algorithm also reconstructs the path from parent links.

Learning goals

  • Compute the longest path between two vertices of a DAG
  • Explain why the longest simple path is hard on graphs with cycles
  • Rebuild the path itself

Prerequisites

DAG DP patterns

The longest chain of dependent tasks decides how long a project takes. On a DAG that is a one-pass computation; remove the no-cycle guarantee and the same question becomes one of the classic hard problems.

37.03.1

Longest path in DAG

Process vertices in topological order and relax each arrow with max instead of min: longest[v] = max(longest[v], longest[u] + w). A vertex's value is final when it is reached, because all its predecessors came earlier. Cost O(n + m). Vertices not reachable from the source keep "none".

Weights may be negative here too. The first option of the DAG animation, *Longest path from the source*, prints the longest path found and its length.

Java
1static long longestPathDag(int n, int[][] edges, int s, int t) {    // Long.MIN_VALUE when t is unreachable from s
2    int[] order = topoOrder(n, edges);
3    long[] best = new long[n];
4    Arrays.fill(best, Long.MIN_VALUE);
5    best[s] = 0;
6    for (int u : order) {
7        if (best[u] == Long.MIN_VALUE) continue;
8        for (int[] e : edges)
9            if (e[0] == u && best[u] + e[2] > best[e[1]]) best[e[1]] = best[u] + e[2];
10    }
11    return best[t];
12}
13
14static int[] topoOrder(int n, int[][] edges) {                      // Kahn's order of a DAG
15    int[] indeg = new int[n], order = new int[n];
16    for (int[] e : edges) indeg[e[1]]++;
17    Deque<Integer> q = new ArrayDeque<>();
18    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);
19    int k = 0;
20    while (!q.isEmpty()) {
21        int u = q.poll();
22        order[k++] = u;
23        for (int[] e : edges) if (e[0] == u && --indeg[e[1]] == 0) q.add(e[1]);
24    }
25    return order;
26}

Dynamic programming over a topological order: longest, shortest, count of paths

Interactive · edit the input

Your input

Try

directed graph · 6 vertices · 9 edges

0

d=0

1
2
3
4
5
Vertex being processedSourceReachable (value shown)Done

topological order

0
1
2
3
5
4

best[v]

00
-1
-2
-3
-4
-5
Setup

A DAG has a topological order: 0 → 1 → 2 → 3 → 5 → 4. Processing vertices in that order means every arrow into a vertex has been handled before the vertex is used, so its value is final. The source starts at 0.

Step 1 / 11
Java
1long[] dagBest(int n, List<int[]>[] adj, int[] order, int s, boolean longest) {   // adj[u] = {v, weight}
2    long NONE = longest ? Long.MIN_VALUE : Long.MAX_VALUE;
3    long[] best = new long[n]; Arrays.fill(best, NONE);
4    best[s] = 0;
5    for (int u : order) {                        // topological order: best[u] is final when u is reached
6        if (best[u] == NONE) continue;           // not reachable from s
7        for (int[] e : adj[u]) {
8            long cand = best[u] + e[1];
9            if (best[e[0]] == NONE || (longest ? cand > best[e[0]] : cand < best[e[0]])) best[e[0]] = cand;
10        }
11    }
12    return best;
13}
14long[] countPaths(int n, List<int[]>[] adj, int[] order, int s) {
15    long[] ways = new long[n]; ways[s] = 1;
16    for (int u : order) for (int[] e : adj[u]) ways[e[0]] += ways[u];   // paths into u extend along every arrow out of u
17    return ways;
18}

Live state

0 arrows relaxed

order

[0, 1, 2, 3, 5, 4]

source

0

No condition evaluated on this step
Execution trace (dry run table)Show 11 steps
StepLineStateWhat happens
1L3order=[0, 1, 2, 3, 5, 4] source=0A DAG has a topological order: 0 → 1 → 2 → 3 → 5 → 4. Processing vertices in that order means every arrow into a vertex has been handled before the vertex is used, so its value is final. The source starts at 0.
2L9u=0 v=1 cand=5 best[v]=50 → 1: 0 + 5 = 5. That beats the old value, so best[1] = 5.
3L9u=0 v=2 cand=3 best[v]=30 → 2: 0 + 3 = 3. That beats the old value, so best[2] = 3.
4L9u=1 v=3 cand=11 best[v]=111 → 3: 5 + 6 = 11. That beats the old value, so best[3] = 11.
5L9u=1 v=2 cand=7 best[v]=71 → 2: 5 + 2 = 7. That beats the old value, so best[2] = 7.
6L9u=2 v=4 cand=11 best[v]=112 → 4: 7 + 4 = 11. That beats the old value, so best[4] = 11.
7L9u=2 v=5 cand=9 best[v]=92 → 5: 7 + 2 = 9. That beats the old value, so best[5] = 9.
8L9u=2 v=3 cand=14 best[v]=142 → 3: 7 + 7 = 14. That beats the old value, so best[3] = 14.
9L9u=3 v=5 cand=15 best[v]=153 → 5: 14 + 1 = 15. That beats the old value, so best[5] = 15.
10L9u=3 v=4 cand=15 best[v]=153 → 4: 14 + 1 = 15. That beats the old value, so best[4] = 15.
11L11return=[0, 5, 7, 14, 15, 15] arrows relaxed=9Values: [0, 5, 7, 14, 15, 15] ('-' = not reachable). Every arrow was used exactly once, so the whole computation is O(n + m). The longest path ends at 4 with length 15: 0 → 1 → 2 → 3 → 4 (read back through the parent links).
37.03.2

Why general longest simple path is hard

In a graph with cycles a walk can go round a positive cycle forever, so the longest *walk* is unbounded; the longest **simple path** (no repeated vertex) is the sensible question, and it is NP-hard: no polynomial algorithm is known, and one would imply P = NP. The shortest-path tricks fail because subpaths of a longest simple path need not be longest, and the visited set matters.

The exhaustive search below tries every simple path. On the complete directed graph with n vertices, the number of calls grows factorially: the test run counted 130 calls for n = 6, 652 for 7, 3,914 for 8, 27,400 for 9 and 219,202 for 10, the ratio between steps grows from 5 to 8. Special cases are easy (DAGs, trees, and some structured graphs), and dynamic programming over subsets reaches O(2^n · n²).

Java
1static class LongestSimple {
2    long calls = 0;                                                  // how many times search ran
3    private long best;
4    long longest(int n, int[][] edges, int s, int t) {              // exhaustive over simple paths; Long.MIN_VALUE if none
5        best = Long.MIN_VALUE;
6        calls = 0;
7        search(edges, s, t, 0, new boolean[n]);
8        return best;
9    }
10    private void search(int[][] edges, int u, int t, long cost, boolean[] used) {
11        calls++;
12        if (u == t) { best = Math.max(best, cost); return; }
13        used[u] = true;
14        for (int[] e : edges) if (e[0] == u && !used[e[1]]) search(edges, e[1], t, cost + e[2], used);
15        used[u] = false;
16    }
17}
37.03.3

Reconstructing path

Store with each vertex the predecessor that gave its best value: parent[v] = u whenever longest[u] + w improves longest[v]. After the pass, follow parents from the target back to the source and reverse. If the target was never reached, the path is empty.

The same trick rebuilds shortest paths and critical paths of a project. Ties may give several optimal paths; the parent links record whichever was found first.

Java
1static List<Integer> longestPathVertices(int n, int[][] edges, int s, int t) {   // vertices of a longest path s -> t, or empty
2    int[] order = topoOrder(n, edges);
3    long[] best = new long[n];
4    int[] parent = new int[n];
5    Arrays.fill(best, Long.MIN_VALUE);
6    Arrays.fill(parent, -1);
7    best[s] = 0;
8    for (int u : order) {
9        if (best[u] == Long.MIN_VALUE) continue;
10        for (int[] e : edges)
11            if (e[0] == u && best[u] + e[2] > best[e[1]]) { best[e[1]] = best[u] + e[2]; parent[e[1]] = u; }
12    }
13    LinkedList<Integer> path = new LinkedList<>();
14    if (best[t] == Long.MIN_VALUE) return path;
15    for (int v = t; v != -1; v = parent[v]) path.addFirst(v);
16    return path;
17}
18
19static int[] topoOrder(int n, int[][] edges) {                      // Kahn's order of a DAG
20    int[] indeg = new int[n], order = new int[n];
21    for (int[] e : edges) indeg[e[1]]++;
22    Deque<Integer> q = new ArrayDeque<>();
23    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);
24    int k = 0;
25    while (!q.isEmpty()) {
26        int u = q.poll();
27        order[k++] = u;
28        for (int[] e : edges) if (e[0] == u && --indeg[e[1]] == 0) q.add(e[1]);
29    }
30    return order;
31}

Dynamic programming over a topological order: longest, shortest, count of paths

Interactive · edit the input

Your input

Try

directed graph · 6 vertices · 9 edges

0

d=0

1
2
3
4
5
Vertex being processedSourceReachable (value shown)Done

topological order

0
1
2
3
5
4

best[v]

00
-1
-2
-3
-4
-5
Setup

A DAG has a topological order: 0 → 1 → 2 → 3 → 5 → 4. Processing vertices in that order means every arrow into a vertex has been handled before the vertex is used, so its value is final. The source starts at 0.

Step 1 / 11
Java
1long[] dagBest(int n, List<int[]>[] adj, int[] order, int s, boolean longest) {   // adj[u] = {v, weight}
2    long NONE = longest ? Long.MIN_VALUE : Long.MAX_VALUE;
3    long[] best = new long[n]; Arrays.fill(best, NONE);
4    best[s] = 0;
5    for (int u : order) {                        // topological order: best[u] is final when u is reached
6        if (best[u] == NONE) continue;           // not reachable from s
7        for (int[] e : adj[u]) {
8            long cand = best[u] + e[1];
9            if (best[e[0]] == NONE || (longest ? cand > best[e[0]] : cand < best[e[0]])) best[e[0]] = cand;
10        }
11    }
12    return best;
13}
14long[] countPaths(int n, List<int[]>[] adj, int[] order, int s) {
15    long[] ways = new long[n]; ways[s] = 1;
16    for (int u : order) for (int[] e : adj[u]) ways[e[0]] += ways[u];   // paths into u extend along every arrow out of u
17    return ways;
18}

Live state

0 arrows relaxed

order

[0, 1, 2, 3, 5, 4]

source

0

No condition evaluated on this step
Execution trace (dry run table)Show 11 steps
StepLineStateWhat happens
1L3order=[0, 1, 2, 3, 5, 4] source=0A DAG has a topological order: 0 → 1 → 2 → 3 → 5 → 4. Processing vertices in that order means every arrow into a vertex has been handled before the vertex is used, so its value is final. The source starts at 0.
2L9u=0 v=1 cand=5 best[v]=50 → 1: 0 + 5 = 5. That beats the old value, so best[1] = 5.
3L9u=0 v=2 cand=3 best[v]=30 → 2: 0 + 3 = 3. That beats the old value, so best[2] = 3.
4L9u=1 v=3 cand=11 best[v]=111 → 3: 5 + 6 = 11. That beats the old value, so best[3] = 11.
5L9u=1 v=2 cand=7 best[v]=71 → 2: 5 + 2 = 7. That beats the old value, so best[2] = 7.
6L9u=2 v=4 cand=11 best[v]=112 → 4: 7 + 4 = 11. That beats the old value, so best[4] = 11.
7L9u=2 v=5 cand=9 best[v]=92 → 5: 7 + 2 = 9. That beats the old value, so best[5] = 9.
8L9u=2 v=3 cand=14 best[v]=142 → 3: 7 + 7 = 14. That beats the old value, so best[3] = 14.
9L9u=3 v=5 cand=15 best[v]=153 → 5: 14 + 1 = 15. That beats the old value, so best[5] = 15.
10L9u=3 v=4 cand=15 best[v]=153 → 4: 14 + 1 = 15. That beats the old value, so best[4] = 15.
11L11return=[0, 5, 7, 14, 15, 15] arrows relaxed=9Values: [0, 5, 7, 14, 15, 15] ('-' = not reachable). Every arrow was used exactly once, so the whole computation is O(n + m). The longest path ends at 4 with length 15: 0 → 1 → 2 → 3 → 4 (read back through the parent links).

Practice ladder

Now try it yourself

Easy

  • All Paths From Source to Target

Medium

  • Parallel Courses III
  • Longest Increasing Path in a Matrix

Advanced

  • Longest Cycle in a Graph
  • Largest Color Value in a Directed Graph

Key takeaways

  • Longest path on a DAG: relax with max in topological order, O(n + m); store parents to rebuild it.
  • With cycles the longest simple path is NP-hard; brute force explores factorially many paths.
  • Negative weights are fine on a DAG.