13.21 Dynamic Programming on Graphs

Dynamic programming is easiest when subproblems form a simple order: left to right, bottom to top, short interval to long interval, child before parent.

algorithmsdynamic-programming

13.21 Dynamic Programming on Graphs

Dynamic programming is easiest when subproblems form a simple order: left to right, bottom to top, short interval to long interval, child before parent. Graphs complicate this picture. A graph may contain many paths into the same state, and cycles may destroy any obvious computation order.

Dynamic programming on graphs works when the graph structure still allows dependencies to be evaluated safely. The most common case is a directed acyclic graph, usually called a DAG. In a DAG, states can be processed in topological order, guaranteeing that every dependency is computed before it is used.

This section shows how to treat graph vertices as DP states, graph edges as transitions, and topological order as the evaluation plan.

Problem

How do we apply dynamic programming when the states and transitions form a graph?

The Basic Model

A graph DP usually has:

$$ dp[u] $$

meaning:

the best value, count, or property associated with vertex (u).

Edges define transitions.

If there is an edge:

$$ u \rightarrow v $$

then information can flow from (u) to (v), or from (v) back to (u), depending on the recurrence.

Examples:

number of paths to each node

longest path ending at each node

shortest distance in a DAG

ways to complete a dependency graph

The graph itself becomes the dependency structure.

Why DAGs Matter

Dynamic programming requires an acyclic dependency order.

If:

A depends on B
B depends on C
C depends on A

then none of the states can be computed first.

A directed acyclic graph avoids this problem. It has at least one topological ordering: a sequence of vertices where every directed edge goes from earlier to later.

For example:

A -> B -> D
A -> C -> D

A valid topological order is:

A, B, C, D

Once vertices are processed in this order, every forward dependency is safe.

Recipe: Count Paths in a DAG

Suppose we want the number of paths from a source vertex (s) to every other vertex.

State:

$$ dp[u] $$

Meaning:

number of paths
from s to u

Base case:

$$ dp[s]=1 $$

Transition:

For every edge:

$$ u \rightarrow v $$

add:

$$ dp[u] $$

to:

$$ dp[v] $$

Implementation:

func CountPathsDAG(
    graph [][]int,
    order []int,
    source int,
) []int {

    n := len(graph)
    dp := make([]int, n)

    dp[source] = 1

    for _, u := range order {

        for _, v := range graph[u] {
            dp[v] += dp[u]
        }
    }

    return dp
}

The key requirement is that order must be topological.

Recipe: Longest Path in a DAG

The longest path problem is hard in general graphs, but straightforward in DAGs.

State:

$$ dp[u] $$

Meaning:

length of the longest path
ending at u

Initialize:

dp[u] = 0

for all vertices.

For every edge:

$$ u \rightarrow v $$

update:

$$ dp[v] = \max(dp[v], dp[u]+1) $$

Implementation:

func LongestPathDAG(
    graph [][]int,
    order []int,
) int {

    n := len(graph)
    dp := make([]int, n)

    answer := 0

    for _, u := range order {

        for _, v := range graph[u] {

            dp[v] = max(
                dp[v],
                dp[u]+1,
            )

            answer = max(answer, dp[v])
        }
    }

    return answer
}

This is the same relaxation pattern used in shortest paths, but with max instead of min.

Recipe: Shortest Paths in a DAG

For weighted DAGs, shortest paths can be computed in one topological pass.

State:

$$ dp[u] $$

Meaning:

shortest distance
from source to u

Base case:

$$ dp[source]=0 $$

All other states begin at infinity.

For edge:

$$ u \rightarrow v $$

with weight:

$$ w $$

transition:

$$ dp[v] = \min(dp[v], dp[u]+w) $$

Implementation:

type Edge struct {
    To int
    Weight int
}

func ShortestPathDAG(
    graph [][]Edge,
    order []int,
    source int,
) []int {

    const inf = int(1e9)

    n := len(graph)
    dp := make([]int, n)

    for i := range dp {
        dp[i] = inf
    }

    dp[source] = 0

    for _, u := range order {

        if dp[u] == inf {
            continue
        }

        for _, e := range graph[u] {

            dp[e.To] = min(
                dp[e.To],
                dp[u]+e.Weight,
            )
        }
    }

    return dp
}

Unlike Dijkstra, this works with negative edge weights as long as the graph is acyclic.

Topological Sorting

A topological order can be computed with DFS or indegree counting.

Kahn's algorithm is often the most convenient.

func TopologicalOrder(graph [][]int) []int {

    n := len(graph)
    indegree := make([]int, n)

    for u := 0; u < n; u++ {
        for _, v := range graph[u] {
            indegree[v]++
        }
    }

    queue := []int{}

    for u := 0; u < n; u++ {
        if indegree[u] == 0 {
            queue = append(queue, u)
        }
    }

    order := []int{}

    for len(queue) > 0 {

        u := queue[0]
        queue = queue[1:]

        order = append(order, u)

        for _, v := range graph[u] {

            indegree[v]--

            if indegree[v] == 0 {
                queue = append(queue, v)
            }
        }
    }

    return order
}

If the resulting order contains fewer than (n) vertices, the graph contains a cycle.

Pull Versus Push Transitions

Graph DP can be written in two styles.

Push Style

Process a state and update its neighbors.

for _, u := range order {
    for _, v := range graph[u] {
        dp[v] = combine(dp[v], transition(dp[u], v))
    }
}

This style is common for path counting and shortest paths.

Pull Style

Compute a state from its predecessors.

for _, u := range order {
    for _, p := range reverseGraph[u] {
        dp[u] = combine(dp[u], transition(dp[p], u))
    }
}

This style is useful when the recurrence is naturally defined in terms of incoming edges.

Both are equivalent when implemented carefully.

Handling Multiple Sources

Some graph DP problems have many starting states.

Example:

longest path in any component

In that case, initialize every source appropriately.

For counting paths:

dp[source] = 1

for each source.

For shortest paths:

dp[source] = 0

for each source.

Multiple-source initialization is often cleaner than adding an artificial super-source.

Cycles and Strongly Connected Components

Cycles break simple DP because dependencies can become circular.

For example:

A -> B -> C -> A

The state values may depend on themselves.

There are several possible responses:

  • reject the input if a DAG is required
  • collapse strongly connected components
  • use graph algorithms such as Dijkstra or Bellman-Ford
  • solve equations if the recurrence is probabilistic
  • use iterative relaxation when convergence is guaranteed

The right choice depends on the problem.

Dynamic programming on graphs is simplest and safest on DAGs.

Condensation Graphs

A directed graph can be compressed into strongly connected components. Each component becomes a node. The resulting condensation graph is always a DAG.

This is useful when the recurrence works at the component level.

For example:

inside each strongly connected component:
handle separately

between components:
run DP on the condensation DAG

This pattern appears in reachability, implication graphs, dependency analysis, and compiler optimization.

Common Patterns

Path Counting

$$ dp[v] += dp[u] $$

for every edge (u \rightarrow v).

Longest Path

$$ dp[v] = \max(dp[v], dp[u]+w) $$

Shortest Path in DAG

$$ dp[v] = \min(dp[v], dp[u]+w) $$

Feasibility

$$ dp[v] = dp[v] \lor dp[u] $$

Number of Ways to Finish

Process reverse topological order:

$$ dp[u] = \sum_{u \rightarrow v} dp[v] $$

Example: Course Completion Count

Suppose a course dependency graph is a DAG. An edge:

u -> v

means course u must be completed before course v.

You may want to count the number of ways to reach each course from prerequisite roots, or compute the longest prerequisite chain.

The longest prerequisite chain is exactly longest path in a DAG.

State:

$$ dp[v] $$

Meaning:

longest chain ending at course v

Transition:

$$ dp[v] = \max(dp[v], dp[u]+1) $$

for every prerequisite edge.

Common Mistakes

Forgetting to Topologically Sort

Processing vertices in numeric order only works if numeric order happens to be topological.

Do not assume it.

Ignoring Cycles

If the graph contains cycles, a single topological pass is invalid.

Detect cycles explicitly.

Wrong Edge Direction

If dependencies are reversed, the recurrence computes a different quantity.

Be precise about whether:

u -> v

means:

u leads to v

or:

u depends on v

Bad Initialization

For counting paths, 0 usually means no known paths.

For shortest paths, unreachable states must begin at infinity.

For longest paths, initialization depends on whether empty paths are allowed.

Complexity Analysis

Let:

$$ V $$

be the number of vertices.

Let:

$$ E $$

be the number of edges.

Topological sorting costs:

$$ O(V+E) $$

A single DP pass also costs:

$$ O(V+E) $$

Memory usage:

$$ O(V+E) $$

including the graph.

This makes DAG dynamic programming highly efficient.

Recognizing Graph DP

Strong indicators include:

dependencies

directed acyclic graph

topological order

number of paths

longest chain

workflow states

build systems

course prerequisites

task scheduling

If a problem can be modeled as states connected by acyclic transitions, graph DP should be considered.

Takeaway

Dynamic programming on graphs treats vertices as states and edges as transitions. When the graph is acyclic, topological order gives a safe computation order, allowing path counts, longest paths, shortest paths, feasibility, and dependency metrics to be computed in linear time. The method is powerful because it generalizes many earlier DP patterns: arrays, trees, intervals, and subsets can all be viewed as special dependency graphs. The main discipline is structural: verify the graph is acyclic, choose the correct edge direction, initialize base states carefully, and process states in dependency order.