DP on DAGs: Longest Path, Path Counting & Topological State Propagation

1. Linear-Time Semiring Relaxation on DAGs

Given a Directed Acyclic Graph $G = (V, E)$ with topological ordering $\pi = (v_1, v_2, \dots, v_n)$ such that every directed edge $(u, v) \in E$ satisfies $\text{pos}(u) < \text{pos}(v)$, we can evaluate any associative path algebra in $O(V + E)$ time:

• Shortest Path (even with negative edge weights!): $(\min, +)$ semiring: $dp[v] = \min_{u \to v} (dp[u] + w(u, v))$.
• Longest Path (Critical Path Method / Project Scheduling): $(\max, +)$ semiring: $dp[v] = \max_{u \to v} (dp[u] + w(u, v))$.
• Number of Distinct $s \leadsto v$ Walks: $(+, \times)$ semiring: $\text{ways}[v] = \sum_{u \to v} \text{ways}[u] \pmod{M}$.
• Path Expectation / Probability: If leaving $u$ chooses an out-edge with probability $p(u, v)$, then $\mathbb{E}[\text{len}(u)] = \sum_{u \to v} p(u, v) \cdot (w(u, v) + \mathbb{E}[\text{len}(v)])$ evaluated in reverse topological order.

2. Extending DAG DP to General Directed Graphs via SCC Condensation

What if the input graph $G$ contains directed cycles, and we want to maximize the sum of vertex weights collected along a walk (where each vertex's weight is collected at most once)? Every Strongly Connected Component (SCC) $C_i$ allows visiting all vertices inside $C_i$ and exiting through any outgoing edge! Thus:

1. Run Tarjan's or Kosaraju's algorithm in $O(V + E)$ to partition $G$ into SCCs $C_1, \dots, C_k$.
2. Contract each SCC $C_i$ into a super-node with weight $W(C_i) = \sum_{u \in C_i} w_u$.
3. The quotient graph $G^{\text{SCC}}$ is a guaranteed DAG! Run $O(V + E)$ Longest Path DP on $G^{\text{SCC}}$.

3. Complexity Matrix

4. Reference C++20 Implementation

#include <algorithm>
#include <cstdint>
#include <queue>
#include <vector>

struct DirectedEdge {
    int to;
    long long weight;
};

struct DagPathMetrics {
    bool is_acyclic;
    long long longest_path;   // -INF if t is unreachable from s
    long long num_paths_mod;  // Number of distinct s -> t paths modulo 10^9 + 7
};

// Simultaneous Cycle Detection, Single-Source Longest Path, and Path Counting on a DAG
DagPathMetrics solve_dag_s_to_t(
    int n, const std::vector<std::vector<DirectedEdge>>& adj, int s, int t) {
    constexpr long long NEG_INF = -(1LL << 60);
    constexpr long long MOD = 1'000'000'007LL;

    std::vector<int> in_deg(n, 0);
    for (int u = 0; u < n; ++u) {
        for (const auto& e : adj[u]) ++in_deg[e.to];
    }

    // Push ALL in-degree 0 vertices so Kahn's topological peeling unlocks the entire DAG
    std::queue<int> q;
    for (int u = 0; u < n; ++u) {
        if (in_deg[u] == 0) q.push(u);
    }

    std::vector<long long> dist(n, NEG_INF);
    std::vector<long long> ways(n, 0);
    dist[s] = 0;
    ways[s] = 1;

    int visited_count = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ++visited_count;

        for (const auto& e : adj[u]) {
            if (dist[u] != NEG_INF) {
                dist[e.to] = std::max(dist[e.to], dist[u] + e.weight);
                ways[e.to] = (ways[e.to] + ways[u]) % MOD;
            }
            if (--in_deg[e.to] == 0) {
                q.push(e.to);
            }
        }
    }

    if (visited_count != n) {
        return { false, NEG_INF, 0 }; // Graph contains a directed cycle!
    }
    return { true, dist[t], ways[t] };
}