Dynamic Programming on Directed Acyclic Graphs (DAGs): Topological Sort & Longest Paths

1. The Equivalence of DP State Spaces and DAG Topologies

Any dynamic program defines:

• Vertices (V): Distinct subproblem states (e.g., dp[i][w] in knapsack or dp[mask][u] in TSP).
• Directed Edges (E): Permitted state transitions (e.g., transition from dp[i - 1][w - weight[i]] to dp[i][w]).
• Weights (W): Costs, profits, or probabilities associated with decisions.

If this transition graph contained a directed cycle (e.g., state A depends on B, B depends on C, and C depends on A), circular dependency would make evaluation impossible without simultaneous linear equation solvers. The acyclic property is the defining prerequisite of Dynamic Programming.

2. Longest Path on DAGs in O(V + E) Linear Time

Finding the longest simple path in a general graph is NP-hard. On a DAG, the longest path problem can be solved in O(V + E) time by relaxing edges in topological order:

vector<int> findLongestPath(int V, const vector<vector<pair<int, int>>>& adj) {
    // 1. Compute in-degrees and topological order using Kahn's Algorithm
    vector<int> inDegree(V, 0);
    for (int u = 0; u < V; ++u) {
        for (const auto& edge : adj[u]) {
            inDegree[edge.first]++;
        }
    }

    queue<int> q;
    for (int u = 0; u < V; ++u) {
        if (inDegree[u] == 0) q.push(u);
    }

    vector<int> topo;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (const auto& edge : adj[u]) {
            if (--inDegree[edge.first] == 0) {
                q.push(edge.first);
            }
        }
    }

    // 2. Dynamic Programming over topological ordering
    const int NEG_INF = -1e9;
    vector<int> dist(V, 0); // dist[u] = longest path ending at u

    for (int u : topo) {
        for (const auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            dist[v] = max(dist[v], dist[u] + weight);
        }
    }

    return dist;
}

3. Combinatorial Path Counting modulo 10^9 + 7

Counting the total number of distinct paths from source S to destination T on a DAG follows an identical topological accumulation:

Because edges only flow forward in topological order, every path is counted exactly once without combinatorial duplication.

4. Critical Path Method (CPM) & Automated Pipeline Scheduling

In DevOps build systems (e.g., Bazel, Turborepo) and compiler instruction schedulers, tasks are modeled as DAG nodes with execution duration weights. The Critical Path Method (CPM) determines the minimum possible completion time for the entire pipeline:

• Forward Pass (Early Start & Finish): Traversing in topological order, ES[v] = max_{u → v} EF[u] and EF[v] = ES[v] + duration[v]. The maximum EF across all sink nodes defines the total project duration.
• Backward Pass (Late Start & Finish): Traversing in reverse topological order, LF[u] = min_{u → v} LS[v] and LS[u] = LF[u] - duration[u].
• Slack Identification: The slack time is Slack[u] = LS[u] - ES[u]. Tasks with Slack[u] == 0 form the Critical Path: any delay on these specific tasks delays the entire system.

5. Single-Source Shortest Paths in DAGs with Arbitrary Negative Weights

In general graphs, Dijkstra's algorithm fails catastrophically when edges have negative weights, requiring the slower Bellman-Ford algorithm in O(V × E) time.

However, on a Directed Acyclic Graph, negative cycles are structurally impossible because cycles cannot exist at all! Consequently, relaxing edges in topological order computes Single-Source Shortest Paths (SSSP) in strict linear O(V + E) time, regardless of whether edge weights are positive, zero, or negative.

6. Kahn's BFS Algorithm vs. Tarjan's Post-Order DFS

Topological sorting can be implemented via two primary methodologies:

7. Engineering Invariants & Graph Memory Layouts

• Forward-Star / CSR Graph Compression: For large-scale graph instances (V = 10^6, E = 5 × 10^6), storing edges in pointer-based node lists generates excessive heap allocation overhead. Use Compressed Sparse Row (CSR) arrays with contiguous head, next, and to buffers to maximize L1 instruction and data cache hit rates.
• Combinatorial Overflow Protection: Path counting sums can explode exponentially. Modulo arithmetic (% 1000000007) must wrap every addition. When computing longest paths, initialize unreachable states to a safe negative sentinel (-1e9) rather than INT_MIN to prevent integer underflow during edge relaxation.

8. Algorithmic Comparison: Graph Shortest/Longest Paths