Dynamic Programming on DAGs

A directed acyclic graph supplies a dependency order for path DP. We compute shortest distance, longest distance and path count from a chosen source using one topological sweep. Negative edge weights are harmless in a DAG because no path can cycle to improve indefinitely. The program explicitly rejects any cyclic input rather than applying an invalid vertex order.

Prerequisites: Topological Sorting; adjacency lists; DP aggregation. Related existing lessons: Topological sorting.

Build the idea

1. Recognize the repeated subproblems

   Different source-to-vertex paths share the same suffix choices. A path ending at u can be summarized by an optimal distance or count at u. If all incoming dependencies precede u, these states can be finalized once. With up to 100000 vertices and 200000 edges, linear graph processing is suitable; enumerating every path can be exponential even in an acyclic graph.

2. Define the state

   shortest[v] and longest[v] are optimal source-to-v path weights; ways[v] counts directed paths modulo 10^9+7. INF and −INF represent unreachable distances, while ways zero alone is not a reachability certificate. Parallel edges count as distinct edge-choice paths. The source has one empty path of weight zero, including when source equals target.

3. Derive the transition

   For each finite reachable u in topological order, relax every edge u→v of weight w:minimum for shortest, maximum for longest, and addition for ways. Each incoming last edge defines a path class. Kahn’s indegree process computes an order over the whole graph. If fewer than n vertices are removed, print CYCLIC even if the cycle is unreachable from the queried source.

   $$\mathrm{shortest}\left[v\right]=\min \mathrm{over}\mathrm{incoming}u\mathrm{of}\mathrm{shortest}\left[u\right]+\mathrm{weight}(u,v)$$

4. Base cases and computation order

   Initialize only source distances to zero and ways[source]=1. All other states are unreachable. Topological order guarantees every incoming predecessor has already contributed before v is processed. Skip unreachable u before adding weights. If the target stays INF, print UNREACHABLE; otherwise print its three states. Negative weights do not disturb this dependency order.

5. Correctness and invariant

   Induct along the topological order. Every nonempty source-to-v path has a unique last edge from a finalized predecessor. The minimum/maximum over these candidates gives the optimum, and disjoint edge-choice classes justify the count sum. A directed cycle destroys that one-pass premise; depending on the objective, it may require shortest-path algorithms, cycle detection or a different state space.

6. Work the example

   For edges 1→2:2,1→3:5,2→3:1,2→4:4,3→4:−1, the three source-target paths cost 2,6,4. Shortest is 2, longest 6, count 3. Vertex 3 is finalized with minimum 3 and maximum 5 before its negative edge contributes to vertex 4.

   vertex	shortest	longest	ways
   1	0	0	1
   2	2	2	1
   3	3	5	2
   4	2	6	3

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
#include<utility>
#include<algorithm>
int main(){
    int n,m,s,t;
    std::cin>>n>>m>>s>>t;
    std::vector<std::vector<std::pair<int,long long>>>graph(n+1);
    std::vector<int>indegree(n+1);
    for(int i=0;i<m;++i){
        int u,v;
        long long w;
        std::cin>>u>>v>>w;
        graph[u].push_back({v,w});
        ++indegree[v];
    }
    std::queue<int>ready;
    for(int u=1;u<=n;++u){
        if(!indegree[u]){
            ready.push(u);
        }
    }
    std::vector<int>order;
    while(!ready.empty()){
        int u=ready.front();
        ready.pop();
        order.push_back(u);
        for(auto[v,w]:graph[u]){
            if(--indegree[v]==0){
                ready.push(v);
            }
        }
    }
    if((int)order.size()!=n){
        std::cout<<"CYCLIC\n";
        return 0;
    }
    const long long INF=4000000000000000000LL,MOD=1000000007;
    std::vector<long long>shortest(n+1,INF),longest(n+1,-INF),ways(n+1);
    shortest[s]=longest[s]=0;
    ways[s]=1;
    for(int u:order){
        if(shortest[u]!=INF){
            for(auto[v,w]:graph[u]){
                shortest[v]=std::min(shortest[v],shortest[u]+w);
                longest[v]=std::max(longest[v],longest[u]+w);
                ways[v]=(ways[v]+ways[u])%MOD;
            } // Every predecessor appears before v, even with negative weights.
        }
    }
    if(shortest[t]==INF){
        std::cout<<"UNREACHABLE\n";
    }
    else{
        std::cout<<shortest[t]<<' '<<longest[t]<<' '<<ways[t]<<'\n';
    }
}

Complexity analysis

O(n) vertex states for each objective; each edge performs constant work. Topological sorting and DP both take O(n+m) time with O(n+m) adjacency/state storage. Any DAG path has≤n−1 edges, so distance magnitude<10^14 fits long long.

Example input and output

Read n m source target (1≤n≤100000,0≤m≤200000), then directed edges u v w, vertices 1..n,|w|≤10^9. Print CYCLIC if any directed cycle exists, UNREACHABLE if target cannot be reached, or shortest longest count modulo 10^9+7.

Input

4 5 1 4
1 2 2
1 3 5
2 3 1
2 4 4
3 4 -1

Output

2 6 3

For edges 1→2:2,1→3:5,2→3:1,2→4:4,3→4:−1, the three source-target paths cost 2,6,4. Shortest is 2, longest 6, count 3. Vertex 3 is finalized with minimum 3 and maximum 5 before its negative edge contributes to vertex 4.

Practical applications

Use for dependency networks, acyclic routing and path counts. The existing Graph Algorithms topological lesson is a prerequisite. Dijkstra has a different nonnegative-weight invariant; DAG DP allows negatives by exploiting acyclicity instead.

Check your understanding

Why can this shortest-path DP allow negative edges?

Put it into practice

Enumerate source-target paths in a small DAG and compare all three outputs.