Every shortest path algorithm fights the same enemy: the possibility that some later discovery loops back and undercuts an earlier conclusion. Dijkstra buys safety with a heap and a no-negatives rule, and Bellman-Ford buys it with brute repetition. On a directed acyclic graph, the enemy doesn't exist. Nothing loops back, so processing nodes in topological order and relaxing each edge exactly once produces every shortest distance in O(V + E), negative weights included, no heap anywhere.

This is the payoff page for topological sort: the ordering it produces is precisely the processing schedule that makes single-pass relaxation sound.

Take five nodes in topological order A, B, C, D, E with edges A→B(3), A→C(6), B→C(4), B→D(4), B→E(11), C→D(8), C→E(11), and one negative edge, D→E(-4). Processing A sets B = 3 and C = 6. Processing B sets D = 7 and E = 14. C improves nothing. Now D takes its turn carrying that -4 edge: predict what happens to E's 14.

It collapses to 3, via A→B→D→E = 3 + 4 - 4. Worth savoring: Dijkstra on this graph would have finalized E at 14 and never looked back, because 14 beat D's 7 plus anything non-negative. The topological pass never finalizes by cheapness at all. It just waits until every road into a node has been tried, which the ordering guarantees, and the negative edge gets its say before E's turn arrives.

from collections import deque

def dag_shortest_paths(n: int, edges: list[tuple[int, int, int]], start: int) -> list[float]:
    # edges hold (source, target, weight); negative weights welcome
    graph = {node: [] for node in range(n)}
    in_degree = [0] * n
    for source, target, weight in edges:
        graph[source].append((target, weight))
        in_degree[target] += 1

    # Kahn's topological order
    queue = deque(node for node in range(n) if in_degree[node] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for target, _ in graph[node]:
            in_degree[target] -= 1
            if in_degree[target] == 0:
                queue.append(target)

    # Relax each edge exactly once, in topological order
    INF = float("inf")
    distance = [INF] * n
    distance[start] = 0

    for node in order:
        # Unreached nodes can't improve anything
        if distance[node] == INF:
            continue

        for target, weight in graph[node]:
            if distance[node] + weight < distance[target]:
                distance[target] = distance[node] + weight

    return distance

The correctness argument fits in two sentences. In topological order, every predecessor of a node comes before it, so by the time a node's turn arrives, every edge into it has already been relaxed and its distance can never improve again. That's the same finality Dijkstra buys with a heap and a no-negatives contract, obtained instead from pure structure, which is why edge signs stop mattering.

The comparison across the family is stark. Bellman-Ford re-relaxes every edge up to V - 1 times because a cycle might exist. Dijkstra pays a log factor to sort the frontier by distance. The DAG pass relaxes each edge exactly once and pays neither cost, making it the fastest shortest-path algorithm there is, on the graphs that permit it.

Here's the twist that makes this page more than a footnote: finding the longest path in a general graph is famously intractable, with no known polynomial algorithm. On a DAG, flip min to max in the relaxation (or negate every weight) and the identical single pass computes longest paths in the same O(V + E).

That flip has a famous job title: the critical path method. Model a project's tasks as nodes, dependencies as edges, durations as weights, and the longest path through the DAG is the chain of tasks that determines the soonest possible finish. Every scheduling tool that reports "this task is on the critical path" is running this page's algorithm with the comparison flipped.

Explicit weighted DAGs appear in scheduling problems like Parallel Courses III, where each course's finish time is its duration plus the latest prerequisite finish, computed straight down the topological order. Implicit DAGs hide in grids: Longest Increasing Path in a Matrix treats each cell as a node with edges to strictly larger neighbors (the strictness is what forbids cycles), and the standard memoized-DFS solution is this page's algorithm running on the implicit ordering recursion provides.

You might think a technique this specialized rarely applies. Acyclic structure is everywhere dependencies are: build graphs, spreadsheet formulas, version histories, neural network layers. When the arrows can't loop, reach for the ordered pass before anything heavier.

Five habits for the family's fastest member:

Two checks first: why is a node's distance final the moment its topological turn arrives, and what single change converts the pass from shortest paths to critical paths? The set leans on the implicit-DAG recognition skill: