37.02Intermediate / Advanced4 topics17 min4 interactive animations

Multi-state graph DP

When a constraint such as a number of stops, a number of colours or a remaining budget matters, the state becomes (vertex, counter); the counter turns an arbitrary graph with cycles into layers that form a DAG.

Learning goals

Add a counter to the state and describe the layers
Count walks of exactly j edges and cheapest walks of at most k edges
Handle a resource budget and a colour limit

Prerequisites

DAG DP patternsShortest paths

A route with at most two stops, a path that may touch at most one dangerous room, a trip with a fuel limit: the vertex alone is not enough to describe where you are. Add what else matters to the state and the problem becomes a plain DP again.

37.02.1

Color-count paths

Colour the vertices; suppose odd-numbered ones are *red* and a walk may visit at most c red vertices. The state is (vertex, reds used so far). Entering a red vertex moves the count from r to r + 1; moves that would exceed c are dropped. Counting walks of exactly L edges is then a table of L + 1 layers.

Even if the graph has cycles, the layers do not: each step goes from layer j to layer j + 1. Choose the fourth option of the layered DP animation; the counts per number of reds appear in every vertex label.

Java

1static long countColourPaths(int n, int[][] edges, int s, int t, boolean[] red, int maxReds, int length) {   // walks with exactly length edges
2    long[][] cur = new long[n][maxReds + 1];                       // cur[v][r]: walks ending at v with r red visits
3    int r0 = red[s] ? 1 : 0;
4    if (r0 <= maxReds) cur[s][r0] = 1;
5    for (int j = 1; j <= length; j++) {
6        long[][] next = new long[n][maxReds + 1];
7        for (int[] e : edges) {
8            int add = red[e[1]] ? 1 : 0;
9            for (int r = 0; r + add <= maxReds; r++) next[e[1]][r + add] += cur[e[0]][r];
10        }
11        cur = next;
12    }
13    long total = 0;
14    for (long x : cur[t]) total += x;
15    return total;
16}

Multi-state graph DP: the state is (vertex, extra counter)

Interactive · edit the input

layer 0 · 5 vertices · 8 edges

Vertex being computedHas a value in this layerSource / target

j = 0

Setup

W[j][v] counts walks from 0 to v with exactly j edges. With j = 0 only the source has a walk (the empty one). Extending a walk by one arrow gives W[j][v] = sum of W[j-1][u] over arrows u → v. Cycles are fine, because j limits the length.

Step 1 / 5

Java

1static long[] walkCounts(int n, int[][] edges, int s, int t, int k) {   // walks s -> t with exactly j edges, j = 0..k
2    long[] cur = new long[n];
3    cur[s] = 1;
4    long[] out = new long[k + 1];
5    out[0] = cur[t];
6    for (int j = 1; j <= k; j++) {
7        long[] next = new long[n];
8        for (int[] e : edges) next[e[1]] += cur[e[0]];   // every walk with j - 1 edges extends along every arrow
9        cur = next;
10        out[j] = cur[t];
11    }
12    return out;
13}
14static long cheapestAtMost(int n, int[][] edges, int s, int t, int k) {   // Long.MAX_VALUE when t needs more than k edges
15    long INF = Long.MAX_VALUE / 2;
16    long[] dist = new long[n];
17    Arrays.fill(dist, INF);
18    dist[s] = 0;
19    for (int j = 1; j <= k; j++) {
20        long[] next = dist.clone();                       // keeping the old value means "at most j edges"
21        for (int[] e : edges) if (dist[e[0]] < INF && dist[e[0]] + e[2] < next[e[1]]) next[e[1]] = dist[e[0]] + e[2];
22        dist = next;
23    }
24    return dist[t] >= INF ? Long.MAX_VALUE : dist[t];
25}
26static int fewestEdgesWithinBudget(int n, int[][] edges, int s, int t, int budget) {   // weights >= 1; -1 if impossible
27    int INF = Integer.MAX_VALUE / 2;
28    int[][] f = new int[budget + 1][n];               // f[b][v]: fewest edges to reach v spending at most b
29    for (int[] row : f) Arrays.fill(row, INF);
30    f[0][s] = 0;
31    for (int b = 0; b <= budget; b++) {
32        if (b > 0) f[b] = f[b - 1].clone();
33        for (int[] e : edges)
34            if (e[2] <= b && f[b - e[2]][e[0]] < INF) f[b][e[1]] = Math.min(f[b][e[1]], f[b - e[2]][e[0]] + 1);
35    }
36    return f[budget][t] >= INF ? -1 : f[budget][t];
37}
38static long walksWithFewReds(int n, int[][] edges, int s, int t, int length, int maxReds) {   // odd vertices are red; every visit counts
39    long[][] cur = new long[n][maxReds + 1];
40    int r0 = s % 2;
41    if (r0 <= maxReds) cur[s][r0] = 1;
42    for (int j = 1; j <= length; j++) {
43        long[][] next = new long[n][maxReds + 1];
44        for (int[] e : edges) {
45            int red = e[1] % 2;
46            for (int r = 0; r + red <= maxReds; r++) next[e[1]][r + red] += cur[e[0]][r];
47        }
48        cur = next;
49    }
50    long total = 0;
51    for (long x : cur[t]) total += x;
52    return total;
53}

Live state

0 layers computed

source

target

No condition evaluated on this step

Execution trace (dry run table)Show 5 steps

Step	Line	State	What happens
1	L3	source=0 target=4	W[j][v] counts walks from 0 to v with exactly j edges. With j = 0 only the source has a walk (the empty one). Extending a walk by one arrow gives W[j][v] = sum of W[j-1][u] over arrows u → v. Cycles are fine, because j limits the length.
2	L8	j=1 W[1][4]=0	Layer 1: 0 walks of exactly 1 edge from 0 to 4.
3	L8	j=2 W[2][4]=1	Layer 2: 1 walk of exactly 2 edges from 0 to 4.
4	L8	j=3 W[3][4]=3	Layer 3: 3 walks of exactly 3 edges from 0 to 4.
5	L12	return=[0, 0, 1, 3]	Walks from 0 to 4 by length 0..3: [0, 0, 1, 3]. Each layer needs one pass over the edges: O(k · m) in total.

37.02.2

Paths with limited stops

*Cheapest flight with at most k stops* limits the number of edges to k + 1. Let cost[j][v] be the cheapest way to reach v using at most j edges. Layer j comes from layer j - 1 by relaxing every edge once: this is Bellman-Ford stopped after k + 1 rounds, which is why it works for graphs with cycles.

It is essential to relax from the **previous** layer's values, not the ones just updated in this round; otherwise a path could use more than j edges in one round. The code copies the array each layer. Compare Dijkstra, which ignores the stop count and can return a cheaper route that uses too many stops.

Java

1static long cheapestWithStops(int n, int[][] flights, int s, int t, int maxStops) {   // flights {from, to, price}; -1 when impossible
2    long INF = Long.MAX_VALUE / 2;
3    long[] cost = new long[n];
4    Arrays.fill(cost, INF);
5    cost[s] = 0;
6    for (int edgesUsed = 0; edgesUsed <= maxStops; edgesUsed++) {    // at most maxStops + 1 edges
7        long[] next = cost.clone();                                  // relax from the previous layer only
8        for (int[] f : flights)
9            if (cost[f[0]] < INF && cost[f[0]] + f[2] < next[f[1]]) next[f[1]] = cost[f[0]] + f[2];
10        cost = next;
11    }
12    return cost[t] >= INF ? -1 : cost[t];
13}

Multi-state graph DP: the state is (vertex, extra counter)

Interactive · edit the input

layer 0 · 5 vertices · 8 edges

Vertex being computedHas a value in this layerSource / target

j = 0

Setup

Step 1 / 5

Java

1static long[] walkCounts(int n, int[][] edges, int s, int t, int k) {   // walks s -> t with exactly j edges, j = 0..k
2    long[] cur = new long[n];
3    cur[s] = 1;
4    long[] out = new long[k + 1];
5    out[0] = cur[t];
6    for (int j = 1; j <= k; j++) {
7        long[] next = new long[n];
8        for (int[] e : edges) next[e[1]] += cur[e[0]];   // every walk with j - 1 edges extends along every arrow
9        cur = next;
10        out[j] = cur[t];
11    }
12    return out;
13}
14static long cheapestAtMost(int n, int[][] edges, int s, int t, int k) {   // Long.MAX_VALUE when t needs more than k edges
15    long INF = Long.MAX_VALUE / 2;
16    long[] dist = new long[n];
17    Arrays.fill(dist, INF);
18    dist[s] = 0;
19    for (int j = 1; j <= k; j++) {
20        long[] next = dist.clone();                       // keeping the old value means "at most j edges"
21        for (int[] e : edges) if (dist[e[0]] < INF && dist[e[0]] + e[2] < next[e[1]]) next[e[1]] = dist[e[0]] + e[2];
22        dist = next;
23    }
24    return dist[t] >= INF ? Long.MAX_VALUE : dist[t];
25}
26static int fewestEdgesWithinBudget(int n, int[][] edges, int s, int t, int budget) {   // weights >= 1; -1 if impossible
27    int INF = Integer.MAX_VALUE / 2;
28    int[][] f = new int[budget + 1][n];               // f[b][v]: fewest edges to reach v spending at most b
29    for (int[] row : f) Arrays.fill(row, INF);
30    f[0][s] = 0;
31    for (int b = 0; b <= budget; b++) {
32        if (b > 0) f[b] = f[b - 1].clone();
33        for (int[] e : edges)
34            if (e[2] <= b && f[b - e[2]][e[0]] < INF) f[b][e[1]] = Math.min(f[b][e[1]], f[b - e[2]][e[0]] + 1);
35    }
36    return f[budget][t] >= INF ? -1 : f[budget][t];
37}
38static long walksWithFewReds(int n, int[][] edges, int s, int t, int length, int maxReds) {   // odd vertices are red; every visit counts
39    long[][] cur = new long[n][maxReds + 1];
40    int r0 = s % 2;
41    if (r0 <= maxReds) cur[s][r0] = 1;
42    for (int j = 1; j <= length; j++) {
43        long[][] next = new long[n][maxReds + 1];
44        for (int[] e : edges) {
45            int red = e[1] % 2;
46            for (int r = 0; r + red <= maxReds; r++) next[e[1]][r + red] += cur[e[0]][r];
47        }
48        cur = next;
49    }
50    long total = 0;
51    for (long x : cur[t]) total += x;
52    return total;
53}

Live state

0 layers computed

source

target

No condition evaluated on this step

Execution trace (dry run table)Show 5 steps

Step	Line	State	What happens
1	L3	source=0 target=4	W[j][v] counts walks from 0 to v with exactly j edges. With j = 0 only the source has a walk (the empty one). Extending a walk by one arrow gives W[j][v] = sum of W[j-1][u] over arrows u → v. Cycles are fine, because j limits the length.
2	L8	j=1 W[1][4]=0	Layer 1: 0 walks of exactly 1 edge from 0 to 4.
3	L8	j=2 W[2][4]=1	Layer 2: 1 walk of exactly 2 edges from 0 to 4.
4	L8	j=3 W[3][4]=3	Layer 3: 3 walks of exactly 3 edges from 0 to 4.
5	L12	return=[0, 0, 1, 3]	Walks from 0 to 4 by length 0..3: [0, 0, 1, 3]. Each layer needs one pass over the edges: O(k · m) in total.

37.02.3

Edge count constraints

With a constraint on the **exact** number of edges, W[j][v] counts walks from the source to v with exactly j edges: W[j][v] = sum of W[j-1][u] over arrows u → v. This is the matrix power of the adjacency matrix in disguise: entry (s, v) of A^j. Parallel arrows and self-loops are counted as separate steps.

Walks, not paths, because vertices may repeat; the length bound keeps the count finite on cyclic graphs. The animation's first option prints one row per j.

Java

1static long[] walkCounts(int n, int[][] edges, int s, int t, int k) {   // walks s -> t with exactly j edges, j = 0..k
2    long[] cur = new long[n];
3    cur[s] = 1;
4    long[] out = new long[k + 1];
5    out[0] = cur[t];
6    for (int j = 1; j <= k; j++) {
7        long[] next = new long[n];
8        for (int[] e : edges) next[e[1]] += cur[e[0]];               // every walk with j - 1 edges extends along every arrow
9        cur = next;
10        out[j] = cur[t];
11    }
12    return out;
13}

Multi-state graph DP: the state is (vertex, extra counter)

Interactive · edit the input

layer 0 · 5 vertices · 8 edges

Vertex being computedHas a value in this layerSource / target

j = 0

Setup

Step 1 / 5

Java

1static long[] walkCounts(int n, int[][] edges, int s, int t, int k) {   // walks s -> t with exactly j edges, j = 0..k
2    long[] cur = new long[n];
3    cur[s] = 1;
4    long[] out = new long[k + 1];
5    out[0] = cur[t];
6    for (int j = 1; j <= k; j++) {
7        long[] next = new long[n];
8        for (int[] e : edges) next[e[1]] += cur[e[0]];   // every walk with j - 1 edges extends along every arrow
9        cur = next;
10        out[j] = cur[t];
11    }
12    return out;
13}
14static long cheapestAtMost(int n, int[][] edges, int s, int t, int k) {   // Long.MAX_VALUE when t needs more than k edges
15    long INF = Long.MAX_VALUE / 2;
16    long[] dist = new long[n];
17    Arrays.fill(dist, INF);
18    dist[s] = 0;
19    for (int j = 1; j <= k; j++) {
20        long[] next = dist.clone();                       // keeping the old value means "at most j edges"
21        for (int[] e : edges) if (dist[e[0]] < INF && dist[e[0]] + e[2] < next[e[1]]) next[e[1]] = dist[e[0]] + e[2];
22        dist = next;
23    }
24    return dist[t] >= INF ? Long.MAX_VALUE : dist[t];
25}
26static int fewestEdgesWithinBudget(int n, int[][] edges, int s, int t, int budget) {   // weights >= 1; -1 if impossible
27    int INF = Integer.MAX_VALUE / 2;
28    int[][] f = new int[budget + 1][n];               // f[b][v]: fewest edges to reach v spending at most b
29    for (int[] row : f) Arrays.fill(row, INF);
30    f[0][s] = 0;
31    for (int b = 0; b <= budget; b++) {
32        if (b > 0) f[b] = f[b - 1].clone();
33        for (int[] e : edges)
34            if (e[2] <= b && f[b - e[2]][e[0]] < INF) f[b][e[1]] = Math.min(f[b][e[1]], f[b - e[2]][e[0]] + 1);
35    }
36    return f[budget][t] >= INF ? -1 : f[budget][t];
37}
38static long walksWithFewReds(int n, int[][] edges, int s, int t, int length, int maxReds) {   // odd vertices are red; every visit counts
39    long[][] cur = new long[n][maxReds + 1];
40    int r0 = s % 2;
41    if (r0 <= maxReds) cur[s][r0] = 1;
42    for (int j = 1; j <= length; j++) {
43        long[][] next = new long[n][maxReds + 1];
44        for (int[] e : edges) {
45            int red = e[1] % 2;
46            for (int r = 0; r + red <= maxReds; r++) next[e[1]][r + red] += cur[e[0]][r];
47        }
48        cur = next;
49    }
50    long total = 0;
51    for (long x : cur[t]) total += x;
52    return total;
53}

Live state

0 layers computed

source

target

No condition evaluated on this step

Execution trace (dry run table)Show 5 steps

Step	Line	State	What happens
1	L3	source=0 target=4	W[j][v] counts walks from 0 to v with exactly j edges. With j = 0 only the source has a walk (the empty one). Extending a walk by one arrow gives W[j][v] = sum of W[j-1][u] over arrows u → v. Cycles are fine, because j limits the length.
2	L8	j=1 W[1][4]=0	Layer 1: 0 walks of exactly 1 edge from 0 to 4.
3	L8	j=2 W[2][4]=1	Layer 2: 1 walk of exactly 2 edges from 0 to 4.
4	L8	j=3 W[3][4]=3	Layer 3: 3 walks of exactly 3 edges from 0 to 4.
5	L12	return=[0, 0, 1, 3]	Walks from 0 to 4 by length 0..3: [0, 0, 1, 3]. Each layer needs one pass over the edges: O(k · m) in total.

37.02.4

Resource-constrained paths

A **budget** works like a counter that is spent: the state is (vertex, amount spent), and the layers are the amounts. If every edge costs at least 1, an edge from layer b - w to layer b always goes forward, so the order of layers is a topological order. The question *fewest edges within total cost B* becomes f[b][v] = min(f[b-1][v], f[b-w][u] + 1).

When costs can be 0 or the budget is huge, plain DP over amounts is too slow or ill-founded, and the problem needs Dijkstra on the states instead. Here the budget is small. Try the *Budget too small* preset to see an answer of -1.

Java

1static int fewestEdgesWithinBudget(int n, int[][] edges, int s, int t, int budget) {   // edges {u, v, cost >= 1}; -1 if impossible
2    int INF = Integer.MAX_VALUE / 2;
3    int[][] f = new int[budget + 1][n];                               // f[b][v]: fewest edges to reach v spending at most b
4    for (int[] row : f) Arrays.fill(row, INF);
5    f[0][s] = 0;
6    for (int b = 0; b <= budget; b++) {
7        if (b > 0) f[b] = f[b - 1].clone();
8        for (int[] e : edges)
9            if (e[2] <= b && f[b - e[2]][e[0]] < INF) f[b][e[1]] = Math.min(f[b][e[1]], f[b - e[2]][e[0]] + 1);
10    }
11    return f[budget][t] >= INF ? -1 : f[budget][t];
12}

Multi-state graph DP: the state is (vertex, extra counter)

Interactive · edit the input

layer 0 · 5 vertices · 8 edges

Vertex being computedHas a value in this layerSource / target

j = 0

Setup

Step 1 / 5

Java

1static long[] walkCounts(int n, int[][] edges, int s, int t, int k) {   // walks s -> t with exactly j edges, j = 0..k
2    long[] cur = new long[n];
3    cur[s] = 1;
4    long[] out = new long[k + 1];
5    out[0] = cur[t];
6    for (int j = 1; j <= k; j++) {
7        long[] next = new long[n];
8        for (int[] e : edges) next[e[1]] += cur[e[0]];   // every walk with j - 1 edges extends along every arrow
9        cur = next;
10        out[j] = cur[t];
11    }
12    return out;
13}
14static long cheapestAtMost(int n, int[][] edges, int s, int t, int k) {   // Long.MAX_VALUE when t needs more than k edges
15    long INF = Long.MAX_VALUE / 2;
16    long[] dist = new long[n];
17    Arrays.fill(dist, INF);
18    dist[s] = 0;
19    for (int j = 1; j <= k; j++) {
20        long[] next = dist.clone();                       // keeping the old value means "at most j edges"
21        for (int[] e : edges) if (dist[e[0]] < INF && dist[e[0]] + e[2] < next[e[1]]) next[e[1]] = dist[e[0]] + e[2];
22        dist = next;
23    }
24    return dist[t] >= INF ? Long.MAX_VALUE : dist[t];
25}
26static int fewestEdgesWithinBudget(int n, int[][] edges, int s, int t, int budget) {   // weights >= 1; -1 if impossible
27    int INF = Integer.MAX_VALUE / 2;
28    int[][] f = new int[budget + 1][n];               // f[b][v]: fewest edges to reach v spending at most b
29    for (int[] row : f) Arrays.fill(row, INF);
30    f[0][s] = 0;
31    for (int b = 0; b <= budget; b++) {
32        if (b > 0) f[b] = f[b - 1].clone();
33        for (int[] e : edges)
34            if (e[2] <= b && f[b - e[2]][e[0]] < INF) f[b][e[1]] = Math.min(f[b][e[1]], f[b - e[2]][e[0]] + 1);
35    }
36    return f[budget][t] >= INF ? -1 : f[budget][t];
37}
38static long walksWithFewReds(int n, int[][] edges, int s, int t, int length, int maxReds) {   // odd vertices are red; every visit counts
39    long[][] cur = new long[n][maxReds + 1];
40    int r0 = s % 2;
41    if (r0 <= maxReds) cur[s][r0] = 1;
42    for (int j = 1; j <= length; j++) {
43        long[][] next = new long[n][maxReds + 1];
44        for (int[] e : edges) {
45            int red = e[1] % 2;
46            for (int r = 0; r + red <= maxReds; r++) next[e[1]][r + red] += cur[e[0]][r];
47        }
48        cur = next;
49    }
50    long total = 0;
51    for (long x : cur[t]) total += x;
52    return total;
53}

Live state

0 layers computed

source

target

No condition evaluated on this step

Execution trace (dry run table)Show 5 steps

Step	Line	State	What happens
1	L3	source=0 target=4	W[j][v] counts walks from 0 to v with exactly j edges. With j = 0 only the source has a walk (the empty one). Extending a walk by one arrow gives W[j][v] = sum of W[j-1][u] over arrows u → v. Cycles are fine, because j limits the length.
2	L8	j=1 W[1][4]=0	Layer 1: 0 walks of exactly 1 edge from 0 to 4.
3	L8	j=2 W[2][4]=1	Layer 2: 1 walk of exactly 2 edges from 0 to 4.
4	L8	j=3 W[3][4]=3	Layer 3: 3 walks of exactly 3 edges from 0 to 4.
5	L12	return=[0, 0, 1, 3]	Walks from 0 to 4 by length 0..3: [0, 0, 1, 3]. Each layer needs one pass over the edges: O(k · m) in total.

Practice ladder

Now try it yourself

Easy

Find if Path Exists in Graph

Medium

Cheapest Flights Within K Stops
Minimum Cost to Reach Destination in Time
Number of Ways to Arrive at Destination

Advanced

Shortest Path in a Grid with Obstacles Elimination

Key takeaways

Add what matters to the state: (vertex, counter) where the counter is stops, edges, colours or money spent.
The counter makes layers; layers form a DAG even when the graph has cycles.
Cheapest with at most k edges: relax from the previous layer only, k + 1 rounds.
Costs of at least 1 make the budget a forward-only counter; zero costs need Dijkstra on the states.