Longest path in a DAG by topological DP

Why this matters

A project has tasks, and some tasks must wait for others. You cannot paint a wall before the plaster is dry. A project manager needs two numbers: the earliest day each task can start, and the total time for the whole project. The total time is set by one chain of tasks that cannot be made shorter. That chain is the longest path through the task graph.

This lesson finds that longest path with dynamic programming (DP). In DP you solve small pieces first, store each answer, and reuse the stored answers. Here the pieces are the vertices of a graph, and the order in which we solve them comes from the shape of the graph.

The graphs module (24-cpp-graphs) covers graph basics. This lesson only needs the idea of an adjacency list, which is explained below.

Graphs, edges and paths

A graph is a set of vertices (the dots, also called nodes) and edges (the lines that join them). A directed edge has an arrow, so it leads from one vertex to another and not back. A weight is a number attached to an edge. In a task graph the weight is usually the number of days a task takes.

A path is a walk along edges that follow their arrows. Its length is the sum of the weights of the edges it uses. A cycle is a path that comes back to the vertex where it started.

A directed acyclic graph, written DAG (say "dag"), is a directed graph with no cycles. "Acyclic" means "without cycles".

Take three tasks: wash (2 days), cook (4 days) and serve (1 day). wash must finish before cook starts, and cook must finish before serve starts. Draw the arrows wash to cook and cook to serve. You cannot get from serve back to wash, so this graph is a DAG.

In code a graph is stored as an adjacency list: for each vertex, a list of the edges that leave it. In C++ this is a std::vector<std::vector<Edge>>. Each Edge holds the vertex it points to and its weight. If graph[3] holds the edge {5, 2}, there is an edge from vertex 3 to vertex 5 with weight 2.

The key idea: visit vertices in topological order

A topological order is a list of all the vertices in which every edge goes from an earlier vertex to a later one. Every DAG has at least one topological order. A graph with a cycle has none, because on a cycle some vertex would have to come before itself.

Here is why the order matters. Suppose we want the longest path that starts at a source vertex s. Let dist[v] be the length of the longest path from s to v found so far. Process the vertices in topological order. When we reach vertex v, every edge into v starts at a vertex that comes earlier in the order. Those vertices were already processed, so their dist values will not change again. That means dist[v] is final at the moment we reach it.

So one pass through the vertices is enough. Each dist[v] is computed from answers that are already stored. That is the dynamic programming pattern: a bigger answer is built from smaller answers that were solved first.

The update for one edge is called relaxing the edge. For an edge from u to v with weight w, the candidate is dist[u] + w. If the candidate is greater than dist[v], we set dist[v] to the candidate and record parent[v] = u. The parent record lets us rebuild the path afterwards.

A small case: vertices 0 and 1, an edge from 0 to 1 with weight 3, and dist[0] = 0. The candidate for vertex 1 is 0 + 3 = 3. Vertex 1 has no path yet, so dist[1] is "no path", and 3 is greater than that. Set dist[1] = 3 and parent[1] = 0.

Vertices that cannot be reached from the source must keep a "no path" marker. The program below uses the smallest possible long long value for this. Using 0 would be a mistake, explained in the common mistakes section.

Step 1: find a topological order with Kahn's algorithm

Kahn's algorithm is one common way to get a topological order. It uses the in-degree of each vertex, which is the number of edges that point into it.

A vertex with in-degree 0 has no unfinished prerequisites, so it can go first. Put it in the order. Then remove its outgoing edges, which lowers the in-degree of each vertex it pointed to. Any vertex whose in-degree drops to 0 is now ready. Keep a queue of ready vertices, and repeat until the queue is empty. A queue is a line: the vertex added first is taken out first.

Here is the walk on the graph used in worked example 1 below. Its edges are 0 -> 1 (weight 3), 0 -> 2 (2), 1 -> 3 (4), 2 -> 3 (6), 2 -> 4 (1), 3 -> 5 (2) and 4 -> 5 (7). The in-degrees start as: vertex 0 has 0, vertex 1 has 1, vertex 2 has 1, vertex 3 has 2, vertex 4 has 1, vertex 5 has 2.

Look at step 4. Vertex 3 has in-degree 2, from vertices 1 and 2. Vertex 1 was taken in step 2, which lowered it to 1. Vertex 2 was taken in step 3, which lowered it to 0, so vertex 3 entered the queue. Every edge goes from an earlier number to a later number in the final order, so this is a topological order.

If the algorithm ends with fewer vertices in the order than the graph has, there is a cycle. The vertices on the cycle each wait for another vertex on the cycle, so none of them ever reaches in-degree 0. The code checks for this and throws an error.

Step 2: relax the edges once

After the order is known, the second step is one loop. Go through the vertices in order. For each vertex u that has a path from the source, relax every edge that leaves it. When the loop ends, dist[v] holds the longest path length for every vertex v.

The loop does not need to repeat. Each edge is relaxed once, when its starting vertex is processed. By then the starting vertex's dist value is final, so the candidate is correct.

The time is the number of vertices plus the number of edges, written O(V + E). Each vertex is visited once, and each edge is looked at once.

The complete program

The file below is the tested program. It has the topological order, the longest path code, path recovery, a deliberately wrong version used later, and four examples. The examples print the results shown in the worked examples.

#include <algorithm>
#include <iostream>
#include <limits>
#include <queue>
#include <stdexcept>
#include <string>
#include <vector>
 
struct Edge {
    int to;
    int weight;
};
 
using Graph = std::vector<std::vector<Edge>>;
 
constexpr long long kNoPath = std::numeric_limits<long long>::min();
 
std::vector<int> topological_order(const Graph& graph) {
    const int n = static_cast<int>(graph.size());
    std::vector<int> indegree(n, 0);
    for (const auto& edges : graph) {
        for (const Edge& e : edges) {
            ++indegree[e.to];
        }
    }
 
    std::queue<int> ready;
    for (int v = 0; v < n; ++v) {
        if (indegree[v] == 0) {
            ready.push(v);
        }
    }
 
    std::vector<int> order;
    order.reserve(n);
    while (!ready.empty()) {
        const int u = ready.front();
        ready.pop();
        order.push_back(u);
        for (const Edge& e : graph[u]) {
            if (--indegree[e.to] == 0) {
                ready.push(e.to);
            }
        }
    }
 
    if (static_cast<int>(order.size()) != n) {
        throw std::invalid_argument("graph has a cycle");
    }
    return order;
}
 
struct LongestPaths {
    std::vector<long long> dist;
    std::vector<int> parent;
};
 
LongestPaths longest_paths_from(const Graph& graph, int source) {
    const int n = static_cast<int>(graph.size());
    LongestPaths result{std::vector<long long>(n, kNoPath), std::vector<int>(n, -1)};
    result.dist[source] = 0;
 
    for (int u : topological_order(graph)) {
        if (result.dist[u] == kNoPath) {
            continue;
        }
        for (const Edge& e : graph[u]) {
            const long long candidate = result.dist[u] + e.weight;
            if (candidate > result.dist[e.to]) {
                result.dist[e.to] = candidate;
                result.parent[e.to] = u;
            }
        }
    }
    return result;
}
 
std::vector<int> recover_path(const LongestPaths& lp, int target) {
    std::vector<int> path;
    if (lp.dist[target] == kNoPath) {
        return path;
    }
    for (int v = target; v != -1; v = lp.parent[v]) {
        path.push_back(v);
    }
    std::reverse(path.begin(), path.end());
    return path;
}
 
// Wrong on purpose: relaxes vertices in index order instead of topological order.
std::vector<long long> buggy_index_order(const Graph& graph, int source) {
    const int n = static_cast<int>(graph.size());
    std::vector<long long> dist(n, kNoPath);
    dist[source] = 0;
    for (int u = 0; u < n; ++u) {
        if (dist[u] == kNoPath) {
            continue;
        }
        for (const Edge& e : graph[u]) {
            dist[e.to] = std::max(dist[e.to], dist[u] + e.weight);
        }
    }
    return dist;
}
 
int main() {
    // Example 1: vertices 0..5, weighted edges.
    Graph g(6);
    g[0] = {{1, 3}, {2, 2}};
    g[1] = {{3, 4}};
    g[2] = {{3, 6}, {4, 1}};
    g[3] = {{5, 2}};
    g[4] = {{5, 7}};
 
    LongestPaths lp = longest_paths_from(g, 0);
    std::cout << "Example 1 distances from 0:\n";
    for (int v = 0; v < static_cast<int>(g.size()); ++v) {
        std::cout << "  vertex " << v << ": " << lp.dist[v] << "\n";
    }
    std::cout << "Path to 5:";
    for (int v : recover_path(lp, 5)) {
        std::cout << ' ' << v;
    }
    std::cout << "\n\n";
 
    // Example 2: tasks as vertices. Edge u -> v with weight duration(u)
    // means v cannot start until u has finished.
    const std::vector<std::string> names = {"start", "design", "build", "test", "docs", "release"};
    const std::vector<int> duration = {0, 3, 5, 2, 4, 1};
    Graph p(names.size());
    p[0] = {{1, duration[0]}};
    p[1] = {{2, duration[1]}, {4, duration[1]}};
    p[2] = {{3, duration[2]}};
    p[3] = {{5, duration[3]}};
    p[4] = {{5, duration[4]}};
 
    LongestPaths sched = longest_paths_from(p, 0);
    std::cout << "Example 2 earliest start times:\n";
    long long finish = 0;
    for (int v = 0; v < static_cast<int>(names.size()); ++v) {
        std::cout << "  " << names[v] << " starts at " << sched.dist[v] << "\n";
        finish = std::max(finish, sched.dist[v] + duration[v]);
    }
    std::cout << "Project length: " << finish << " days\n";
    std::cout << "Critical path:";
    for (int v : recover_path(sched, 5)) {
        std::cout << ' ' << names[v];
    }
    std::cout << "\n\n";
 
    // Example 3: index order gives a wrong answer when edges point to lower indexes.
    Graph back(3);
    back[2] = {{1, 5}};
    back[1] = {{0, 1}};
    std::vector<long long> wrong = buggy_index_order(back, 2);
    LongestPaths right = longest_paths_from(back, 2);
    std::cout << "Example 3 vertex 0, index order: " << wrong[0] << "\n";
    std::cout << "Example 3 vertex 0, topological order: " << right.dist[0] << "\n\n";
 
    // Example 4: a cycle makes the graph not a DAG.
    Graph cyc(3);
    cyc[0] = {{1, 1}};
    cyc[1] = {{2, 1}};
    cyc[2] = {{0, 1}};
    try {
        longest_paths_from(cyc, 0);
    } catch (const std::invalid_argument& err) {
        std::cout << "Example 4 error: " << err.what() << "\n";
    }
    return 0;
}

Compile and run it with:

g++ -std=c++20 -Wall -o dag31 dag31.cpp
./dag31

The compiler printed no warnings, and the program printed this (g++ 15.2.0 on Linux):

Example 1 distances from 0:
  vertex 0: 0
  vertex 1: 3
  vertex 2: 2
  vertex 3: 8
  vertex 4: 3
  vertex 5: 10
Path to 5: 0 2 3 5
 
Example 2 earliest start times:
  start starts at 0
  design starts at 0
  build starts at 3
  test starts at 8
  docs starts at 3
  release starts at 10
Project length: 11 days
Critical path: start design build test release
 
Example 3 vertex 0, index order: -9223372036854775808
Example 3 vertex 0, topological order: 6
 
Example 4 error: graph has a cycle

Worked example 1: a small graph with a tie

Start with the graph from the Kahn walk. The source is vertex 0, and the order is 0, 1, 2, 3, 4, 5.

Process each vertex in turn:

• Vertex 0 has dist 0. Relax 0 -> 1: candidate 3, so dist[1] = 3, parent 0. Relax 0 -> 2: candidate 2, so dist[2] = 2, parent 0.
• Vertex 1 has dist 3. Relax 1 -> 3: candidate 3 + 4 = 7, so dist[3] = 7, parent 1.
• Vertex 2 has dist 2. Relax 2 -> 3: candidate 2 + 6 = 8. This is greater than 7, so dist[3] = 8 and parent becomes 2. Relax 2 -> 4: candidate 3, so dist[4] = 3, parent 2.
• Vertex 3 has dist 8. Relax 3 -> 5: candidate 8 + 2 = 10, so dist[5] = 10, parent 3.
• Vertex 4 has dist 3. Relax 4 -> 5: candidate 3 + 7 = 10. This is equal to 10, not greater, so nothing changes. The parent of 5 stays 3.

Vertex 3 was reached in two ways. The path through 1 gives 7, and the path through 2 gives 8. The larger one wins. Vertex 5 was also reached in two ways that both give 10. The program keeps the first one it found, because the test is "greater than" and not "greater than or equal to". The path is therefore 0, 2, 3, 5. The other path with the same length is 0, 2, 4, 5. Either is a correct answer.

The rebuilt path is the list from the target back to the source, following parent: 5, then 3, then 2, then 0. The program reverses it, which gives 0 2 3 5.

Worked example 2: a project schedule

Now model a real case. A small website launch has five tasks, plus a start vertex that gives the graph one starting point. Each task has a duration. The rule is: an edge from u to v has weight equal to the duration of u, which means v cannot start before u has finished.

The start vertex has duration 0. It has one edge, to design, with weight 0. That makes design start at day 0.

The earliest start time of a task is the longest path length from start to that task. For release, there are two ways in. Through design, build and test, the path length is 0 + 3 + 5 + 2 = 10. Through design and docs, it is 0 + 3 + 4 = 7. The longer one, 10, is the earliest start, so release starts at day 10.

The project length is the largest value of start + duration over all tasks. The program computes this as 11 days, which is release starting at 10 plus its 1 day.

The critical path is the chain that sets the project length: start, design, build, test, release. A task on the critical path cannot slip without delaying the whole project. docs is not on it. It can finish at day 7 and release still starts at day 10. The 3 spare days are called slack. Tasks with no slack are the ones to watch.

Worked example 3: a graph with a cycle

Suppose one task depends on itself, directly or through other tasks. Here three tasks form a loop: 0 -> 1 -> 2 -> 0.

Kahn's algorithm starts with the vertices whose in-degree is 0. In this loop every vertex has in-degree 1, so the queue starts empty. The order has 0 vertices, which is not 3. The code throws std::invalid_argument with the message "graph has a cycle". Example 4 in the program catches it and prints that message.

If the exception is not caught, C++ stops the program and prints a message like this. This output comes from a short sample that throws the same exception type with the same message:

terminate called after throwing an instance of 'std::invalid_argument'
  what():  graph has a cycle

The text after what(): is the message passed to the exception. The exit code is 134, which means the program was stopped by an abort signal.

Common mistakes

Relaxing vertices in index order. A common first attempt loops over the vertex numbers 0, 1, 2, ... and relaxes their edges. This works only when every edge goes from a lower number to a higher number. The buggy_index_order function in the program shows the failure. Its graph has edges 2 -> 1 (weight 5) and 1 -> 0 (weight 1). The loop visits vertex 0 first, when it has no value yet, and then vertex 1, which also has no value yet, so it is skipped. Only then does vertex 2 set dist[1] = 5. The edge 1 -> 0 is never used, because vertex 1 has already been passed. The program printed -9223372036854775808 for vertex 0. That number is the "no path" marker, which means the code reports that vertex 0 cannot be reached. The correct answer is 6 (2 -> 1 -> 0, which is 5 + 1), and the topological version prints it.

Using 0 as the "no path" marker. If dist starts at 0 for every vertex, an unreachable vertex looks like it has a path of length 0. The code then treats it as reachable, and a later relaxation from it can produce a wrong answer. Use a marker that cannot be a real length, such as the smallest long long value, and check for it before reading an edge.

Forgetting the cycle check. If the code does not compare the size of the order with the number of vertices, the vertices on a cycle are never processed. They keep the "no path" marker, and the program prints wrong distances without any error. The check in topological_order is what catches this case.

Mixing up > and <. Longest path uses "greater than" when relaxing. Shortest path uses "less than" and a different marker for "not reached". Changing one without the other gives wrong answers with no error message.

Warnings about comparing a signed loop counter with size(). The code for (int v = 0; v < dist.size(); ++v) compiles, but with -Wall g++ prints a warning:

warn31.cpp: In function ‘int main()’:
warn31.cpp:6:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    6 |     for (int v = 0; v < dist.size(); ++v) {
      |                     ~~^~~~~~~~~~~~

The fix is to store the size in an int first, as the program does with const int n = static_cast<int>(graph.size());, or to use std::size_t for the counter.

Practice

Exercise 1: a longest path by hand

A DAG has vertices 0 to 4 and these weighted edges: 0 -> 1 (2), 0 -> 2 (5), 1 -> 2 (1), 2 -> 3 (2), 1 -> 4 (5) and 3 -> 4 (1). Use source 0 and the order 0, 1, 2, 3, 4. Find the longest path from 0 to 4 and its length.

Show the answer

The longest path has length 8. It is 0, 2, 3, 4, with lengths 5, 2 and 1. Relaxing gives dist[1] = 2, dist[2] = 5 (from 0, since 2 + 1 = 3 is smaller), dist[3] = 7, and then dist[4] is 7 from vertex 1 and 8 from vertex 3. The 8 wins.

Exercise 2: why index order fails

The graph has vertices 0 to 3 and edges 3 -> 1 (weight 4) and 1 -> 0 (weight 2). The source is 3. If you relax vertices in the order 0, 1, 2, 3, what is dist[0] at the end? What is the correct value, and why does the order matter?

Show the answer

The loop gives dist[0] as "no path". Vertex 1 is skipped at the moment it is visited, because its dist is still "no path". Vertex 3 sets dist[1] = 4 only after vertex 1 has already been passed. The correct value is 6, which is the path 3 -> 1 -> 0 with length 4 + 2. The order matters because vertex 1 must be processed after vertex 3 has set its value, and the edge 1 -> 0 must be relaxed after vertex 1 is final. A topological order puts 3 before 1 and 1 before 0.

Exercise 3: a longest path that can start anywhere

Change longest_paths_from so that the path may start at any vertex. You are not given a source. Use the graph from worked example 1. What is the longest path length in the whole graph?

Show the answer

Set dist[v] = 0 for every vertex at the start, and skip the source assignment. Run the same loop. Each dist[v] then holds the longest path that ends at v and may start anywhere. The answer is the largest value in dist. For worked example 1 it is 10, at vertex 5. Both 0 -> 2 -> 3 -> 5 and 0 -> 2 -> 4 -> 5 reach 10. A brute-force check over all start and end pairs also gives 10.

Exercise 4: shortest path instead of longest

Using the graph from worked example 1 and source 0, what changes are needed to find the shortest path to each vertex? What is the shortest distance to vertex 5, and which path gives it?

Show the answer

Replace the "no path" marker with a very large value, such as std::numeric_limits<long long>::max(). Skip vertices whose dist equals that large value. Change the test to "less than" and the candidate to min. The shortest distance to vertex 5 is 9, along 0 -> 1 -> 3 -> 5, which is 3 + 4 + 2. The other two paths, 0 -> 2 -> 3 -> 5 and 0 -> 2 -> 4 -> 5, both have length 10. The same topological order works for this change, and it also works when some weights are negative, because the DAG has no cycles.

Exercise 5: a small project

Four tasks: A takes 2 days, B takes 4 days, C takes 1 day and D takes 3 days. A must finish before B and C start. B and C must both finish before D starts. Each edge weight is the duration of the task it leaves, as in worked example 2. Find the earliest start of each task, the project length, and the critical path.

Show the answer

Edges are A -> B (2), A -> C (2), B -> D (4) and C -> D (1). A starts at 0, B and C start at 2, and D starts at max(2 + 4, 2 + 1) = 6. The finish times are A at 2, B at 6, C at 3 and D at 9. The project length is 9 days. The critical path is A, B, D, because D waits for B. C finishes at day 3 and has 3 days of slack.

Summary

• A DAG is a directed graph with no cycles, and a topological order puts every edge from an earlier vertex to a later one.
• Kahn's algorithm builds a topological order using in-degrees and a queue. If not every vertex is placed, the graph has a cycle.
• Processing vertices in topological order makes each dist[v] final when it is reached, so one relaxation pass is enough.
• Relaxing an edge means setting dist[v] to dist[u] + weight when that is larger, and recording the parent.
• Use a "no path" marker that cannot be a real length, and check it before using a value.
• In a task graph, the longest path is the critical path, and the difference between a task's latest and earliest start is its slack.