Part 7: DAGs, Topological Sorting & Critical Path Method

A Bit of History

Project scheduling on a graph has two parallel origin stories, both from the late 1950s and both born from genuinely high-stakes engineering. In 1957, chemical company DuPont, working with computer manufacturer Remington Rand, developed the Critical Path Method (CPM) to plan plant construction and maintenance shutdowns — famously reducing one plant shutdown from 125 hours to 78 hours in an early trial. Almost simultaneously and independently, the US Navy developed PERT (Program Evaluation and Review Technique) in 1958 to manage the staggeringly complex Polaris submarine-launched ballistic missile program — a project with an estimated 3,000 contractors. Both methods model a project as a graph of tasks with dependencies; CPM assumed known task durations, while PERT added probabilistic duration estimates. The two approaches converged over the following decade into the hybrid CPM/PERT scheduling techniques still used by project-management software today.

Directed Acyclic Graphs

A directed acyclic graph (DAG) is exactly what its name says: a directed graph with no directed cycles. Recall that a vertex with in-degree 0 is a source and one with out-degree 0 is a sink; every DAG has at least one of each (a purely cyclic graph, by contrast, can have neither).

Real Dependency Graphs

DAGs are everywhere the moment "X depends on Y" appears: course prerequisites (you can't take Graph Theory 401 before Discrete Math 101), build systems (a compiled object file depends on its source and headers — exactly what GNU Make's dependency graph encodes), package managers (npm, pip, and Cargo all resolve install order via a topological sort of the dependency DAG — and reject a dependency cycle as an error), task schedulers (a CI/CD pipeline's stages), and data pipelines (Apache Airflow's DAG abstraction is literally named after this structure).

Topological Sorting

A topological order of a directed graph is a linear ordering of vertices such that for every edge \((u,v)\), \(u\) appears before \(v\). Claim: a topological order exists if and only if the graph is acyclic.

Proof. (\(\implies\), contrapositive) If a cycle \(v_1 \to v_2 \to \cdots \to v_k \to v_1\) exists, no linear order can place every \(v_i\) before its successor and \(v_k\) before \(v_1\) simultaneously — a direct contradiction. (\(\impliedby\)) If the graph is acyclic, repeatedly remove any source vertex (one must exist — a proof by contradiction: if every vertex had positive in-degree, following in-edges backward forever would eventually repeat a vertex, producing a cycle) and append it to the order; the remaining graph is still acyclic and smaller, so induction on the number of vertices completes the argument.

DFS-Based Topological Sort

Part 6 previewed the result: run DFS across the whole graph, and list vertices in decreasing order of finish time. Because every edge \((u,v)\) in a DAG satisfies \(f[u] > f[v]\) (a back edge — the only way this could fail — cannot exist in an acyclic graph), this ordering always respects every dependency. Cost: \(O(V+E)\), inherited directly from DFS.

Kahn's Algorithm (Preview)

An entirely different, BFS-flavored strategy repeatedly removes vertices with in-degree 0 (maintaining a queue of them), decrementing the in-degree of their neighbors as edges are conceptually removed. If the algorithm exhausts before all vertices are output, the graph had a cycle — this is often the cleanest way to detect a cycle and produce an order in the same pass.

DAG Dynamic Programming

A topological order turns a DAG into the perfect substrate for dynamic programming: process vertices in topological order, and by the time you reach vertex \(v\), every vertex that could influence \(v\)'s value has already been finalized. This single observation is why DAG shortest paths and DAG longest paths are both solvable in \(O(V+E)\) — dramatically faster than Dijkstra's \(O((V+E)\log V)\) — and, remarkably, DAG shortest/longest paths work correctly even with negative edge weights, since the topological order (not a priority queue) is what guarantees correctness here.

def dag_shortest_paths(topo_order, adj, source):
    """
    topo_order: vertices in topological order (source must come first).
    adj: dict[vertex] -> list[(neighbor, weight)]. Works with negative weights.
    """
    dist = {v: float('inf') for v in topo_order}
    dist[source] = 0
    for u in topo_order:
        if dist[u] == float('inf'):
            continue
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w        # single relaxation pass suffices
    return dist

# For longest paths: negate all weights, run shortest-path DP, negate the result.
def dag_longest_paths(topo_order, adj, source):
    neg_adj = {u: [(v, -w) for v, w in edges] for u, edges in adj.items()}
    neg_dist = dag_shortest_paths(topo_order, neg_adj, source)
    return {v: -d if d != float('inf') else float('-inf') for v, d in neg_dist.items()}

The Critical Path Method

Model a project as a DAG: each activity is a vertex weighted by its duration, and an edge \(A \to B\) means "\(A\) must finish before \(B\) can start." Four DAG-DP passes compute everything a project manager needs:

• Earliest Start / Earliest Finish (forward pass, topological order): \(\text{ES}(v) = \max_{u \to v} \text{EF}(u)\), \(\text{EF}(v) = \text{ES}(v) + \text{duration}(v)\).
• Latest Start / Latest Finish (backward pass, reverse topological order): \(\text{LF}(v) = \min_{v \to w} \text{LS}(w)\), \(\text{LS}(v) = \text{LF}(v) - \text{duration}(v)\).
• Slack: \(\text{slack}(v) = \text{LS}(v) - \text{ES}(v)\) — how much \(v\) can be delayed without delaying the whole project.
• Critical path: the sequence of zero-slack activities — this is the DAG longest path from source to sink, and it determines the minimum possible project duration.

Worked Example

A tiny software-release project: Design (3 days) \(\to\) Backend (5 days) and Frontend (4 days) in parallel, both \(\to\) Integration Testing (2 days) \(\to\) Release (1 day).

Activity	Duration	ES	EF	LS	LF	Slack
Design	3	0	3	0	3	0
Backend	5	3	8	3	8	0
Frontend	4	3	7	4	8	1
Integration Testing	2	8	10	8	10	0
Release	1	10	11	10	11	0

The critical path is Design \(\to\) Backend \(\to\) Integration Testing \(\to\) Release (all zero slack), giving a minimum project duration of 11 days. Frontend has 1 day of slack — it could start a day late, or run a day long, without delaying the release. This is exactly the information DuPont's engineers used in 1957 to know which tasks in a plant shutdown could not slip a single day, and which had breathing room.

Exercises

1. Add a new activity "Documentation" (2 days) that depends only on Design and must finish before Release. Recompute ES/EF/LS/LF/slack for every activity, and state whether the critical path changes.
2. Prove that every DAG has at least one topological order, but that order is generally not unique — construct a small DAG with at least two valid topological orders.
3. Explain, using the DAG-DP argument, why DAG shortest paths work correctly with negative weights even though Dijkstra's algorithm does not.
4. Challenge: Implement the forward and backward CPM passes as two separate DAG-DP computations (using the topological order from the DFS-based sort in this part), and verify your results match the worked example's table.

Conclusion & Next Steps

A single ordering — topological order — unlocks both a linear-time dynamic-programming framework for shortest/longest paths and, via the Critical Path Method, a genuinely practical project-scheduling tool with a 65-year engineering track record. Next, we turn from acyclic structure to the general question of connectivity: cycles, components, and the vertices and edges whose removal would break a graph apart.