Shortest Paths on DAGs

On a DAG, shortest paths are a linear-time DP — no priority queue, no relaxation rounds, and negative weights are perfectly fine. Always check whether your graph is acyclic before reaching for Dijkstra.

SSSP in $O(V+E)$

Process vertices in topological order and relax outgoing edges. Once a vertex is reached in topological order, no future vertex can improve it, because every path into it comes from earlier vertices.

vector<long long> ssspDAG(int n, vector<vector<pair<int,long long>>>& adj, int s) {
    vector<int> order = topoOrder(n, adj);            // Kahn or DFS
    const long long INF = LLONG_MAX / 4;
    vector<long long> dist(n, INF);
    dist[s] = 0;
    for (int u : order) {
        if (dist[u] == INF) continue;
        for (auto [v, w] : adj[u])
            dist[v] = min(dist[v], dist[u] + w);
    }
    return dist;
}

Longest path in $O(V+E)$

Longest path is NP-hard on general graphs. On a DAG it is the same loop with max, or equivalently: negate every weight, run SSSP, negate the answers back.

for (int u : order) {
    if (dp[u] == NEG_INF) continue;
    for (auto [v, w] : adj[u]) dp[v] = max(dp[v], dp[u] + w);
}

This is the standard solution to critical path / project scheduling (PERT): the longest path through a task DAG is the minimum possible completion time.

Why this beats everything else

Algorithm	Time	Negative weights	Needs a DAG
BFS	$O(V+E)$	no (unweighted only)	no
Topological DP	$O(V+E)$	yes	yes
Dijkstra	$O(E\log V)$	no	no
Bellman-Ford	$O(VE)$	yes	no
Floyd-Warshall	$O(V^3)$	yes	no

Other DAG DPs, all the same loop

Once you have a topological order, every one of these is one pass:

Question	Recurrence
Number of paths $s\to t$	$\mathrm{cnt}[v]={\sum }_{u\to v}\mathrm{cnt}[u]$
Longest path ending at $v$	$\mathrm{dp}[v]={\max }_{u\to v}(\mathrm{dp}[u]+w)$
Number of shortest paths	carry a count alongside the distance, reset on improvement
Reachable set from $v$	process in reverse topological order, union the successors’ sets (bitset)
Minimum path cover of a DAG	$n$ minus the maximum bipartite matching of the split graph (Dilworth)
Longest common subsequence, edit distance, grid paths	these are DAG DPs — the grid is the DAG

Every DP is a DAG shortest path

A DP’s states and transitions form a DAG; “compute in an order where dependencies come first” is exactly topological order. Recognising this makes it obvious why a DP with a cyclic dependency needs Dijkstra or Bellman-Ford instead of a plain loop. See DP on DAGs.

Hidden DAGs

Some graphs are DAGs only after a transformation:

• Condensation. Contract the SCCs of any directed graph and the result is a DAG. Longest path in the condensation, weighted by component size, answers “largest set of mutually reachable vertices along a path”.
• Layered graphs. If state includes “steps used so far” and steps only increase, the state graph is a DAG even when the underlying graph has cycles.
• Grids with monotone movement. Only right/down moves means the grid is a DAG.

See also: Topological Sort · DP on DAGs · Shortest Paths