PK

PKBytes

Explore tracks
Chapter 34: Directed Acyclic Graphs and Topological Ordering
34.04Intermediate / Advanced4 topics16 min4 interactive animations

DAG algorithms

On a DAG the topological order turns hard-looking path problems into one linear pass: longest paths, shortest paths (even with negative weights) and path counts all follow from a dynamic program over the order.

Learning goals

  • Compute single-source longest and shortest paths on a DAG in O(n + m)
  • Explain why negative weights are no problem on a DAG
  • Count paths between two vertices
  • Recognise a DP over a topological order

Prerequisites

Topological sortDynamic programming basics

On a general graph, shortest paths need Dijkstra or Bellman-Ford and longest simple paths are intractable. If the graph has no cycle, the vertices can be processed in an order where everything a vertex depends on is already finished, and each of these problems becomes a short loop.

34.04.1

Longest path in DAG

Let best[v] be the longest path from the source to v. Process vertices in topological order; for each arrow u → v of weight w set best[v] = max(best[v], best[u] + w). When v is reached, every arrow into it has already been used, so its value is final. Total time O(n + m).

On a general graph the longest path is NP-hard, because a cycle lets a path grow without limit; the absence of cycles is what makes this easy. This is the critical-path computation from the previous lesson. Choose *Longest path from the source* in the animation.

Java
1static long[] dagLongest(int n, int[][] edges, int s) {          // edges {u, v, w}; Long.MIN_VALUE = unreachable
2    int[] order = topo(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;
12}
13static int[] topo(int n, int[][] edges) {                        // Kahn's order of a DAG
14    int[] indeg = new int[n], order = new int[n];
15    for (int[] e : edges) indeg[e[1]]++;
16    Deque<Integer> q = new ArrayDeque<>();
17    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);
18    int k = 0;
19    while (!q.isEmpty()) {
20        int u = q.poll();
21        order[k++] = u;
22        for (int[] e : edges) if (e[0] == u && --indeg[e[1]] == 0) q.add(e[1]);
23    }
24    return order;
25}

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).
34.04.2

Shortest path in DAG

The same pass with min gives shortest paths. Dijkstra needs non-negative weights because it settles a vertex before it has seen every route to it. The DAG order guarantees every route into a vertex has been examined before the vertex is used, so **negative weights are fine** here, and no priority queue is needed.

That makes it O(n + m) instead of Dijkstra's O((n + m) log n). Vertices that come before the source in the order, or cannot be reached from it, simply keep "unreachable"; the *Vertices before the source are unreachable* preset shows this.

Java
1static long[] dagShortest(int n, int[][] edges, int s) {          // edges {u, v, w}, negative w allowed; Long.MAX_VALUE = unreachable
2    int[] indeg = new int[n], order = new int[n];
3    for (int[] e : edges) indeg[e[1]]++;
4    Deque<Integer> q = new ArrayDeque<>();
5    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);
6    int k = 0;
7    while (!q.isEmpty()) {
8        int u = q.poll();
9        order[k++] = u;
10        for (int[] e : edges) if (e[0] == u && --indeg[e[1]] == 0) q.add(e[1]);
11    }
12    long[] dist = new long[n];
13    Arrays.fill(dist, Long.MAX_VALUE);
14    dist[s] = 0;
15    for (int u : order) {
16        if (dist[u] == Long.MAX_VALUE) continue;
17        for (int[] e : edges)
18            if (e[0] == u && dist[u] + e[2] < dist[e[1]]) dist[e[1]] = dist[u] + e[2];
19    }
20    return dist;
21}

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).
34.04.3

Count paths

To count the paths from s to every vertex, let ways[s] = 1 and, in topological order, add ways[u] to ways[v] for each arrow u → v. Every path to v ends with exactly one arrow u → v and a path to u, so the sum is the total. Parallel arrows count separately.

Counts grow quickly (a chain of diamonds doubles at each step), so use long or work modulo a prime when the answer would overflow. The animation's *Count the paths* option shows the counts building up.

Java
1static long[] countPaths(int n, int[][] edges, int s) {           // edges {u, v}; ways[v] = number of paths s -> v
2    int[] indeg = new int[n], order = new int[n];
3    for (int[] e : edges) indeg[e[1]]++;
4    Deque<Integer> q = new ArrayDeque<>();
5    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);
6    int k = 0;
7    while (!q.isEmpty()) {
8        int u = q.poll();
9        order[k++] = u;
10        for (int[] e : edges) if (e[0] == u && --indeg[e[1]] == 0) q.add(e[1]);
11    }
12    long[] ways = new long[n];
13    ways[s] = 1;                                                  // the empty path
14    for (int u : order)
15        for (int[] e : edges)
16            if (e[0] == u) ways[e[1]] += ways[u];                 // every path to u extends along this arrow
17    return ways;
18}

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).
34.04.4

DP over topological order

All three problems share a pattern: *the answer for a vertex depends only on its predecessors*. That is exactly a dynamic program whose states are the vertices and whose evaluation order is a topological order. Memoised recursion over the DAG does the same work in a different order.

Other examples are the longest chain in a partial order (the number of edges on the longest path), the number of ways to build something from prerequisites, and many game-state problems. The code below finds the longest path in edges, starting anywhere.

Java
1static int longestChain(int n, int[][] edges) {                   // most arrows on any path; -1 if the graph has a cycle
2    int[] indeg = new int[n], len = new int[n];                   // len[v] = most arrows on a path ending at v
3    for (int[] e : edges) indeg[e[1]]++;
4    Deque<Integer> q = new ArrayDeque<>();
5    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);
6    int seen = 0, best = 0;
7    while (!q.isEmpty()) {
8        int u = q.poll();
9        seen++;
10        best = Math.max(best, len[u]);
11        for (int[] e : edges)
12            if (e[0] == u) {
13                len[e[1]] = Math.max(len[e[1]], len[u] + 1);
14                if (--indeg[e[1]] == 0) q.add(e[1]);
15            }
16    }
17    return seen == n ? best : -1;
18}

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
  • Find All Possible Recipes from Given Supplies

Advanced

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

Key takeaways

  • On a DAG, process vertices in topological order and relax each arrow once: O(n + m).
  • Negative weights are fine on a DAG, and no priority queue is needed.
  • Path counts add the count of each predecessor; use long or a modulus.
  • Any quantity that depends only on predecessors is a DP over a topological order.