Chapter 75

Home

Shortest Path in DAGs

In a Directed Acyclic Graph (DAG), you can find shortest paths in O(V+E) — no priority queue needed. Process nodes in topological order, relax each node's outgoing edges once.

Topological Order Relaxation

C++ — DAG shortest path

vector dag_shortest(vector>>& adj, int start) {
    int V = adj.size();
    vector topo = topological_order(adj);  // from ch.79
    vector dist(V, LLONG_MAX);
    dist[start] = 0;

    for (int u : topo) {
        if (dist[u] == LLONG_MAX) continue;
        for (auto [v, w] : adj[u])
            if (dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
    }
    return dist;
}

// O(V+E) — the fastest possible shortest path algorithm

📐 Why topological order works

In a DAG, processing in topological order guarantees that when you process node u, all paths to u have already been explored. Each node is relaxed exactly once. No cycles means no need to revisit — O(V+E) total.

Key Takeaways