DAG Shortest & Longest Paths

The DAG Advantage

Shortest paths usually feel iterative: discover a promising route, improve it later, and keep revisiting vertices until no better route remains. A DAG removes the reason for that uncertainty. Because its vertices can be arranged so every edge points forward, all possible ways to enter a vertex are known before that vertex is processed.

This single structural fact gives us several unusual freedoms:

The Dynamic-Programming View

Topological relaxation is dynamic programming on a partial order. Every path that ends at $v$ must enter through some incoming edge $(u,v)$, so the best path to $v$ is the best among its predecessor candidates.

The recurrences look circular on an arbitrary graph: $u$ might depend on $v$ while $v$ depends on $u$. In a DAG, topological order breaks that circle. Every predecessor $u$ appears before $v$, so all terms on the right-hand side are final when the algorithm reaches $v$.

Topological Relaxation, Step by Step

1. Compute a topological ordering. Kahn's algorithm conveniently detects a cycle when it emits fewer than $|V|$ vertices.
2. Initialize the source to zero. Initialize every other vertex to the appropriate unreachable sentinel: $+\infty$ for shortest paths or $-\infty$ for longest paths.
3. Visit vertices in topological order. If $u$ is unreachable, skip its outgoing edges so sentinel arithmetic cannot create fake paths.
4. For each edge $(u,v,w)$, compute candidate = dist[u] + w.
5. Accept the candidate when it is smaller for a shortest path or larger for a longest path. Store $u$ as parent[v] if the actual path will be reconstructed.

A Shortest-and-Longest Trace

Consider the topological order $S,A,B,C,T$ and the weighted edges shown below. The edge $A\to B$ has weight $-4$, which lets the shortest-path trace demonstrate why negative weights are harmless in a DAG.

The shortest route is $S\to A\to B\to C\to T$ with weight $2-4+2+1=1$. The longest route is $S\to B\to T$ with weight $6+5=11$. The same edges, order, and loop produce both answers; only the sentinel and comparison operator change.

Why Negative Weights Are Safe

Dijkstra's algorithm depends on nonnegative edges: after extracting the smallest tentative distance, a later route cannot make it smaller. A negative edge breaks that argument. DAG relaxation uses a different guarantee—the topological order proves that all predecessors have already been considered—so an edge weight may be positive, zero, or negative.

There is also no negative cycle to drive a shortest distance toward $-\infty$, because a DAG has no cycle of any weight. Every directed path uses at most $|V|-1$ edges. Consequently, every reachable shortest and longest path has a finite value when edge weights are finite.

Recovering the Actual Path

Distances answer “how much?” but most applications also ask “which route?” Whenever a candidate improves $v$, set parent[v] = u. After relaxation, follow parent pointers backward from the target until reaching the source, then reverse that sequence.

If the target still has the unreachable sentinel, there is no source-to-target path and reconstruction should return an empty result. Equal candidates deserve an explicit policy: keep the first parent for deterministic traversal-order behavior, or add a secondary rule when lexicographic or domain-specific tie-breaking matters.

Critical Path and Slack

In project scheduling, edges can represent activities and weights their durations. The longest distance from Start to an event is its earliest possible occurrence time. The longest Start → End route is the critical path: delaying any activity on it delays the whole project.

A forward maximum pass computes earliest event times. A reverse-topological pass can compute latest permissible times without extending the final duration. Their difference is slack. Zero-slack activities form at least one critical path; multiple critical paths are possible and make a schedule more sensitive to delays.

Implementation

The implementation separates three responsibilities: produce and validate a topological order, relax for either objective, and reconstruct a requested path. Keeping them separate makes the invariants visible and lets one topological order be reused for several sources or related DAG computations.

from collections import deque
from math import inf

def topological_order(n, adj):
    in_degree = [0] * n
    for u in range(n):
        for v, _ in adj[u]:
            in_degree[v] += 1

    queue = deque(u for u in range(n) if in_degree[u] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v, _ in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    return order if len(order) == n else None

def dag_paths(n, adj, source, maximize=False):
    order = topological_order(n, adj)
    if order is None:
        raise ValueError("input graph contains a directed cycle")

    unreachable = -inf if maximize else inf
    dist = [unreachable] * n
    parent = [None] * n
    dist[source] = 0

    for u in order:
        if dist[u] == unreachable:
            continue
        for v, weight in adj[u]:
            candidate = dist[u] + weight
            improves = candidate > dist[v] if maximize else candidate < dist[v]
            if improves:
                dist[v] = candidate
                parent[v] = u

    return dist, parent

def reconstruct_path(parent, source, target):
    path = []
    current = target
    while current is not None:
        path.append(current)
        if current == source:
            return path[::-1]
        current = parent[current]
    return []  # target is unreachable from source

# S=0, A=1, B=2, C=3, T=4
edges = [(0, 1, 2), (0, 2, 6), (1, 2, -4),
         (1, 3, 3), (2, 3, 2), (2, 4, 5), (3, 4, 1)]
n = 5
adj = [[] for _ in range(n)]
for u, v, weight in edges:
    adj[u].append((v, weight))

shortest, short_parent = dag_paths(n, adj, 0)
longest, long_parent = dag_paths(n, adj, 0, maximize=True)

print("Shortest distances:", shortest)              # [0, 2, -2, 0, 1]
print("Shortest S-T path:", reconstruct_path(short_parent, 0, 4))
print("Longest distances:", longest)                # [0, 2, 6, 8, 11]
print("Longest S-T path:", reconstruct_path(long_parent, 0, 4))

#include <algorithm>
#include <iostream>
#include <limits>
#include <queue>
#include <stdexcept>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;
using Edge = pair<int, long long>;

struct PathResult {
    vector<long long> distance;
    vector<int> parent;
};

vector<int> topologicalOrder(const vector<vector<Edge>>& adj) {
    int n = static_cast<int>(adj.size());
    vector<int> inDegree(n, 0);
    for (const auto& edges : adj)
        for (const auto& [v, weight] : edges) {
            (void)weight;
            ++inDegree[v];
        }

    queue<int> ready;
    for (int u = 0; u < n; ++u)
        if (inDegree[u] == 0) ready.push(u);

    vector<int> order;
    while (!ready.empty()) {
        int u = ready.front();
        ready.pop();
        order.push_back(u);
        for (const auto& [v, weight] : adj[u]) {
            (void)weight;
            if (--inDegree[v] == 0) ready.push(v);
        }
    }

    if (static_cast<int>(order.size()) != n)
        throw invalid_argument("input graph contains a directed cycle");
    return order;
}

PathResult dagPaths(const vector<vector<Edge>>& adj, int source,
                    bool maximize = false) {
    const long long POS_INF = numeric_limits<long long>::max() / 4;
    const long long NEG_INF = numeric_limits<long long>::min() / 4;
    const long long unreachable = maximize ? NEG_INF : POS_INF;
    vector<int> order = topologicalOrder(adj);
    vector<long long> dist(adj.size(), unreachable);
    vector<int> parent(adj.size(), -1);
    dist[source] = 0;

    for (int u : order) {
        if (dist[u] == unreachable) continue;
        for (const auto& [v, weight] : adj[u]) {
            long long candidate = dist[u] + weight;
            bool improves = maximize ? candidate > dist[v] : candidate < dist[v];
            if (improves) {
                dist[v] = candidate;
                parent[v] = u;
            }
        }
    }
    return {dist, parent};
}

vector<int> reconstructPath(const vector<int>& parent,
                            int source, int target) {
    vector<int> path;
    for (int at = target; at != -1; at = parent[at]) {
        path.push_back(at);
        if (at == source) {
            reverse(path.begin(), path.end());
            return path;
        }
    }
    return {};
}

int main() {
    vector<tuple<int, int, long long>> edges = {
        {0,1,2}, {0,2,6}, {1,2,-4}, {1,3,3},
        {2,3,2}, {2,4,5}, {3,4,1}
    };
    vector<vector<Edge>> adj(5);
    for (auto [u, v, weight] : edges) adj[u].push_back({v, weight});

    PathResult shortest = dagPaths(adj, 0);
    PathResult longest = dagPaths(adj, 0, true);

    cout << "Shortest distance to T: " << shortest.distance[4] << '\n';
    cout << "Longest distance to T: " << longest.distance[4] << '\n';
}

import java.util.*;

public class DAGShortestPath {
    static final long POS_INF = Long.MAX_VALUE / 4;
    static final long NEG_INF = Long.MIN_VALUE / 4;

    static class PathResult {
        final long[] distance;
        final int[] parent;
        PathResult(long[] distance, int[] parent) {
            this.distance = distance;
            this.parent = parent;
        }
    }

    static List<Integer> topologicalOrder(List<List<long[]>> adj) {
        int n = adj.size();
        int[] inDegree = new int[n];
        for (List<long[]> edges : adj)
            for (long[] edge : edges) inDegree[(int) edge[0]]++;

        Deque<Integer> ready = new ArrayDeque<>();
        for (int u = 0; u < n; ++u)
            if (inDegree[u] == 0) ready.add(u);

        List<Integer> order = new ArrayList<>();
        while (!ready.isEmpty()) {
            int u = ready.remove();
            order.add(u);
            for (long[] edge : adj.get(u)) {
                int v = (int) edge[0];
                if (--inDegree[v] == 0) ready.add(v);
            }
        }

        if (order.size() != n)
            throw new IllegalArgumentException("input graph contains a directed cycle");
        return order;
    }

    static PathResult dagPaths(List<List<long[]>> adj,
                               int source, boolean maximize) {
        List<Integer> order = topologicalOrder(adj);
        long unreachable = maximize ? NEG_INF : POS_INF;
        long[] dist = new long[adj.size()];
        int[] parent = new int[adj.size()];
        Arrays.fill(dist, unreachable);
        Arrays.fill(parent, -1);
        dist[source] = 0;

        for (int u : order) {
            if (dist[u] == unreachable) continue;
            for (long[] edge : adj.get(u)) {
                int v = (int) edge[0];
                long candidate = dist[u] + edge[1];
                boolean improves = maximize
                        ? candidate > dist[v]
                        : candidate < dist[v];
                if (improves) {
                    dist[v] = candidate;
                    parent[v] = u;
                }
            }
        }
        return new PathResult(dist, parent);
    }

    static List<Integer> reconstructPath(int[] parent, int source, int target) {
        List<Integer> path = new ArrayList<>();
        for (int at = target; at != -1; at = parent[at]) {
            path.add(at);
            if (at == source) {
                Collections.reverse(path);
                return path;
            }
        }
        return Collections.emptyList();
    }

    public static void main(String[] args) {
        long[][] edges = {
            {0,1,2}, {0,2,6}, {1,2,-4}, {1,3,3},
            {2,3,2}, {2,4,5}, {3,4,1}
        };
        List<List<long[]>> adj = new ArrayList<>();
        for (int i = 0; i < 5; ++i) adj.add(new ArrayList<>());
        for (long[] edge : edges)
            adj.get((int) edge[0]).add(new long[]{edge[1], edge[2]});

        PathResult shortest = dagPaths(adj, 0, false);
        PathResult longest = dagPaths(adj, 0, true);
        System.out.println("Shortest distance to T: " + shortest.distance[4]);
        System.out.println("Longest distance to T: " + longest.distance[4]);
    }
}

Complexity and Algorithm Choice

Kahn's topological sort scans each vertex and edge once. Relaxation scans each vertex in the order and each outgoing edge once more. Constants add; asymptotic costs do not multiply.

The auxiliary space covers in-degrees, the ready queue, the order, distances, and parents. The adjacency list occupies $O(V+E)$ input space. If many path computations use the same unchanged DAG, cache the topological order and reuse it; each new source then needs only the $O(V+E)$ relaxation phase.

Real-World Applications

Once a dependency graph is acyclic, “best path” becomes a reusable primitive rather than a specialized trick.

Pitfalls and Implementation Checklist

Exercises

1. Repeat the worked trace by hand and record the distance arrays after each vertex. Which entries can still change at every step?
2. Add a disconnected component to the example. Confirm that its vertices occur in the topological order but remain unreachable from $S$.
3. Modify the code to break equal-distance ties by choosing the smaller predecessor ID.
4. Construct a DAG with only negative weights. Explain why initializing longest-path distances to zero would give incorrect answers.
5. Compute latest event times and activity slack for the project diagram using one reverse-topological pass.
6. Add a super-source and solve a multiple-source shortest-path problem.
7. Challenge: count how many distinct shortest paths reach each vertex while preserving the same $O(V+E)$ time bound.

Historical Note

The method unites two classic ideas: topological ordering for dependency structures and relaxation for path optimization. Critical Path Method made the longest-path interpretation especially influential in project planning, while modern graph libraries present DAG shortest paths as a compact example of dynamic programming over a topological order.