Shortest Path in DAGShortest paths on a DAG

01Why it exists

Reach for it when you see:The graph is guaranteed acyclic (dependencies, time only moving forward, positions only moving forward), negative weights but no cycles, a longest path or a critical path, transitions between DP states, counting paths.

02The core idea

On a general graph Dijkstra forbids negative weights, Bellman-Ford allows them but costs O(VE), and the longest path is outright NP-hard. If the graph is a DAG (a directed acyclic graph), though, you can lay its nodes out in topological order, so that every edge points from an earlier node to a later one. Process the nodes in that order and relax each node's outgoing edges once, and you get single-source shortest paths in O(V + E) time, with negative weights causing no trouble at all.

Why it works: by the time node u comes up, every edge into u starts at a node that sits earlier in the order and has therefore already been processed, so dist[u] is final and can no longer change. Any shortest path to v ends with some edge u → v whose u must sit before v; when u's turn came dist[u] was already correct, so relaxing that edge makes dist[v] correct too. Induction along the topological order finishes the proof. A DAG has no cycles, so it has no negative cycles either. Nodes that sit before the source, or that simply cannot be reached from it, stay at ∞ forever, and those nodes must never be relaxed from.

Cost: the topological sort is O(V + E), and relaxation looks at each node and each edge exactly once, which is O(V + E) as well, so O(V + E) time and O(V) extra space in total. For the longest path, just start from −∞ and compare with the maximum instead; alternatively, negate every weight and run the shortest path. The critical path of a project schedule takes two passes: forwards through the topological order for the earliest start times (the longest path), then backwards for the latest start times, with the gap between them being the float. The same order supports plenty of other things, such as ways[v] += ways[u] to count paths. In fact every dynamic program can be read as a shortest or longest path on a DAG whose nodes are the states and whose edges are the transitions.

Common traps: treating a graph as a DAG when it actually has a cycle, which is why Kahn emitting fewer than V nodes has to raise an error; relaxing from a node that is still at ∞, because when ∞ is stored as a large integer, adding a negative weight lands below ∞ and invents a path out of nowhere; assuming the topological order has to start at the source, when in fact you sort the whole graph and the nodes ahead of the source just stay at ∞; initialising the longest path to 0 instead of −∞, which makes unreachable nodes look reachable; and applying the technique to a cyclic graph to find a longest path, which gives the wrong answer. How it relates to the neighbouring lessons: the ordering comes from Topological Sort; on an acyclic graph this is far faster than Bellman-Ford; and Dijkstra can be read as working out a safe processing order as it goes, whereas on a DAG you know the right order in advance.

03The algorithm

1. 1Confirm the graph is acyclic and compute a topological order (Kahn, or the reverse of the DFS finishing order); if Kahn emits fewer than V nodes, there is a cycle.
2. 2Set every dist to ∞ (to −∞ when you want the longest path) and the source to 0. If you need the path itself, keep a parent array as well.
3. 3Take the nodes in topological order. If dist[u] is still ∞, u cannot be reached from the source, so skip it.
4. 4For each outgoing edge u → v with weight w: if dist[u] + w < dist[v] (use > for the longest path), update dist[v] and set parent[v] = u.
5. 5Once every node is done, dist is the answer, and following parent backwards gives the path. For a critical path, make a second pass in reverse topological order to get the latest start times; the tasks with zero float are the ones on the critical path.

04Interactive demo

The tabs at the top switch between two examples, and the row underneath is the topological order together with the current distances: blue is the node being processed, green is one that is finished. In "Shortest path (negative weights)" the source is S, and R comes before S in the order and simply cannot be reached, so it is skipped when its turn comes. After that each outgoing edge turns amber as it is relaxed, and the blue edges are the shortest-path tree so far: Y is first set to 6 via T, then drops to 5 through the negative edge X → Y, while Z starts at 4 and finally becomes 3 through the −2 on Y → Z. In "Longest path: project schedule" the number on an edge is the duration of the task it leaves from, and the update takes the maximum instead: Test has to wait for both API (day 9) and UI (day 7), so it takes 9, and Ship can begin on day 12 at the earliest. The last step marks the critical path Start → Spec → API → Test → Ship and works out the float on UI and Docs.

05Code

Python has Kahn's topological sort followed by relaxation for the shortest path, path reconstruction, and the critical path with its two passes for the total duration and the float. C++ has a version built on the DFS finishing order, plus a word-segmentation example: position numbers are already a topological order, so scoring each dictionary word as an edge weight and taking the longest path splits 研究生命起源 into 研究 生命 起源.

from collections import deque

INF = float("inf")


def topo_order(n, adj):
    """Kahn's topological sort; fewer than n nodes in the output means the graph has a cycle"""
    indeg = [0] * n
    for u in range(n):
        for v, _ in adj[u]:
            indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v, _ in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    if len(order) != n:
        raise ValueError("the graph has a cycle, so it is not a DAG")
    return order


def dag_shortest(n, edges, src):
    """Single-source shortest paths on a DAG, negative weights allowed. Returns (dist, parent), O(V + E)"""
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
    dist, parent = [INF] * n, [-1] * n
    dist[src] = 0
    for u in topo_order(n, adj):
        if dist[u] == INF:                      # unreachable nodes must not be relaxed from
            continue
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v], parent[v] = dist[u] + w, u
    return dist, parent


def critical_path(durations, deps):
    """Project scheduling: durations[i] is the number of days task i takes, deps is a list of (before, after).
    Returns (total duration, float of every task). A task with zero float lies on the critical path"""
    n = len(durations)
    adj = [[] for _ in range(n)]
    for u, v in deps:
        adj[u].append((v, durations[u]))
    order = topo_order(n, adj)
    earliest = [0] * n                          # earliest start = longest path from the start
    for u in order:
        for v, w in adj[u]:
            earliest[v] = max(earliest[v], earliest[u] + w)
    total = max(earliest[i] + durations[i] for i in range(n))
    latest = [total - durations[i] for i in range(n)]   # latest start: any later delays the project
    for u in reversed(order):                   # reverse topological order, working backwards
        for v, w in adj[u]:
            latest[u] = min(latest[u], latest[v] - w)
    return total, [latest[i] - earliest[i] for i in range(n)]


if __name__ == "__main__":
    R, S, T, X, Y, Z = range(6)
    edges = [(R, S, 5), (R, T, 3), (S, T, 2), (S, X, 6), (T, X, 7), (T, Y, 4), (T, Z, 2), (X, Y, -1), (X, Z, 1), (Y, Z, -2)]
    dist, parent = dag_shortest(6, edges, S)
    print(dist)                                 # [inf, 0, 2, 6, 5, 3]
    path, v = [], Z
    while v != -1:
        path.append("RSTXYZ"[v])
        v = parent[v]
    print("".join(reversed(path)))              # SXYZ: 6 + (-1) + (-2) = 3

    # start, spec, backend, frontend, docs, test, ship
    dur = [0, 3, 6, 4, 2, 3, 0]
    deps = [(0, 1), (1, 2), (1, 3), (1, 4), (2, 5), (3, 5), (4, 6), (5, 6)]
    print(critical_path(dur, deps))             # (12, [0, 0, 0, 2, 7, 0, 0])

06Practice

• LeetCode 3243Shortest Distance After Road Addition Queries I (indices only move forward, so rerun the DAG shortest path per query)Medium
• LeetCode 2192All Ancestors of a Node in a Directed Acyclic Graph (pass ancestor sets along the topological order)Medium
• LeetCode 1786Number of Restricted Paths From First to Last Node (Dijkstra first, then count paths in distance order)Medium
• LeetCode 329Longest Increasing Path in a Matrix (longest path on an implicit DAG)Hard
• LeetCode 1857Largest Color Value in a Directed Graph (DP over the topological order, which also detects cycles)Hard