Lesson 9 of 17 · Graphs and trees

The Longest Path in a DAG (DP + Topological Sorting)


In directed acyclic graphs (DAGs) we can efficiently find the longest path (the maximum number of edges or the maximum total weight) using a combination of topological sorting and dynamic programming.

Topological sorting gives us the order in which we can process the nodes, and dynamic programming keeps the best result for every point of processing.

Unlike general directed graphs, where the problem of the longest simple path is hard and cannot be solved with this simple approach, in a DAG we solve this problem in linear time.

This is one of the nicest uses of topological order: we process the nodes only when all their predecessors are already ready.


A DAG before and after topological sorting, with the topological order of the nodes shown
Topological sorting does not change the graph; it finds an order in which every node comes before its successors.

What are we actually looking for?


In the longest path problem we want to find the path that has the greatest total length.

Depending on the task, we can look for the longest path from a given starting node or for the longest path in the whole DAG.

The length can mean:

  • the number of edges on the path (an unweighted graph)
  • the sum of the weights of the edges (a weighted graph)

For example, in the following DAG:


0 → 1 → 3
 \   ↘
  ↘   2 → 4 → 5

There are several possible paths from node 0:


0 → 1 → 3
0 → 1 → 2 → 4
0 → 1 → 2 → 4 → 5

Of all of them, we are interested in the longest one.

Important:

In DAGs we can find the longest path efficiently because there are no cycles that would allow the path to be extended endlessly.

In practice this problem appears when we want to determine:

  • the longest chain of dependencies between tasks
  • the minimum time to finish a project
  • the longest sequence of courses with prerequisites
  • the longest sequence of operations in a production process

A DAG with the longest path from node 0 to node 5 marked
An example of a DAG in which the longest path can be found with topological sorting and DP.

The basic idea of the algorithm


In a DAG we do not have to go backwards or try all the paths. It is enough to order the nodes so that every node comes before its successors. We get that order with topological sorting.

Then we define a DP array:


dp[v]

where dp[v] is the length of the longest path that ends at the node v, looking at the topological order.

If there is an edge u -> v, we can go from u to v and get:


dp[v] = max(dp[v], dp[u] + w(u, v))

where w(u, v) is the weight of the edge. If the graph is unweighted, then w(u, v) = 1.

An important intuition:

The topological order guarantees that when we process the node u, all the paths that enter u have already been processed. That is why one DP pass is enough.

Updating the dp array step by step in a DAG
The DP values are propagated along the edges in topological order.

Two variants of the problem


It is important to tell apart two common versions of the task.

1. The longest path in the whole DAG — the starting node is not given in advance. 2. The longest path from a given starting node — we look for a path that starts at one exactly determined point.

In the first variant we usually compute the longest path that ends at every node and take the maximum at the end. In the second variant we initialise the starting node with zero, and the other nodes with a very small value.

For an unweighted DAG this means:


dp[start] = 0

while all the other nodes are unreachable at the start.



An example of an unweighted DAG



0 → 1 → 3
 \   ↘   ↘
  ↘   2 → 4 → 5

One longest path is:

0 → 1 → 2 → 4 → 5

The length of the path is 4, because it has four edges.

Here it is not important to find just any path, but the one with the largest number of edges.



Implementation: an unweighted DAG


#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    // --------------------------------------------------------
    // The graph and the in-degrees of the nodes
    // --------------------------------------------------------
    //
    // g[u] = the list of all the nodes v for which there is an edge u -> v
    // indeg[v] = the number of edges coming into v
    //
    // We need this array for Kahn's algorithm.
    // --------------------------------------------------------
    vector<vector<int>> g(n);
    vector<int> indeg(n, 0);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;   // the edge a -> b
        g[a].push_back(b);
        indeg[b]++;
    }

    // --------------------------------------------------------
    // Kahn's algorithm for topological sorting
    // --------------------------------------------------------
    //
    // We put all the nodes with indeg = 0 into the queue.
    // These are the nodes that have no predecessors.
    // --------------------------------------------------------
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (indeg[i] == 0)
            q.push(i);
    }

    vector<int> topo;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo.push_back(u);

        // We remove all the edges from u
        for (int v : g[u]) {
            indeg[v]--;
            if (indeg[v] == 0)
                q.push(v);
        }
    }

    // --------------------------------------------------------
    // If we have not processed all the nodes,
    // the graph is not a DAG.
    // This algorithm is meant only for a DAG.
    // --------------------------------------------------------
    if ((int)topo.size() != n) {
        cout << "The graph is not a DAG, so this algorithm cannot be used.\n";
        return 0;
    }

    // --------------------------------------------------------
    // DP:
    // dp[v] = the length of the longest path that ends at v
    // --------------------------------------------------------
    //
    // Since the graph is unweighted, every move adds 1.
    // At the start every node can be the beginning of a path,
    // so we start from 0.
    // --------------------------------------------------------
    vector<int> dp(n, 0);
    vector<int> parent(n, -1);

    for (int u : topo) {
        for (int v : g[u]) {
            if (dp[v] < dp[u] + 1) {
                dp[v] = dp[u] + 1;
                parent[v] = u;
            }
        }
    }

    // --------------------------------------------------------
    // We look for the largest value of dp
    // --------------------------------------------------------
    int end = 0;
    for (int i = 1; i < n; i++) {
        if (dp[i] > dp[end])
            end = i;
    }

    cout << "The longest path in the DAG is: " << dp[end] << "\n";

    // --------------------------------------------------------
    // Reconstructing the path
    // --------------------------------------------------------
    vector<int> path;
    for (int x = end; x != -1; x = parent[x]) {
        path.push_back(x);
    }
    reverse(path.begin(), path.end());

    cout << "Path: ";
    for (int x : path) cout << x << " ";
    cout << "\n";

    return 0;
}

Note:

This variant computes the longest path in the whole DAG. If you want the longest path from one concrete starting node, the initialisation is a little different.


An example with weights



0 -5→ 1 -2→ 3
 \    ↘
  3     7
   ↘     ↘
    2 -1→ 4 -4→ 5

In the weighted variant the goal is to find the path with the greatest total sum of weights.

An important fact:

Negative weights are not a problem for this algorithm, because the graph has no cycles. That is completely different from the shortest path, where negative weights can be a problem.

If there is a starting node, then we use:


dp[start] = 0

and we initialise all the other nodes as unreachable.



Implementation: the longest path from a given starting node


#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll NEG_INF = -(1LL << 60);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, start;
    cin >> n >> m >> start;

    // --------------------------------------------------------
    // A weighted graph: g[u] holds pairs (v, w)
    // where w is the weight of the edge u -> v
    // --------------------------------------------------------
    vector<vector<pair<int,int>>> g(n);
    vector<int> indeg(n, 0);

    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        indeg[b]++;
    }

    // --------------------------------------------------------
    // Kahn's algorithm
    // --------------------------------------------------------
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (indeg[i] == 0)
            q.push(i);
    }

    vector<int> topo;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo.push_back(u);

        for (auto [v, w] : g[u]) {
            indeg[v]--;
            if (indeg[v] == 0)
                q.push(v);
        }
    }

    if ((int)topo.size() != n) {
        cout << "The graph is not a DAG.\n";
        return 0;
    }

    // --------------------------------------------------------
    // DP for the starting node
    // --------------------------------------------------------
    //
    // start is the only node with the value 0.
    // The others are unreachable until we improve them.
    // --------------------------------------------------------
    vector<ll> dp(n, NEG_INF);
    vector<int> parent(n, -1);
    dp[start] = 0;

    for (int u : topo) {
        if (dp[u] == NEG_INF) continue;

        for (auto [v, w] : g[u]) {
            if (dp[v] < dp[u] + w) {
                dp[v] = dp[u] + w;
                parent[v] = u;
            }
        }
    }

    // --------------------------------------------------------
    // The greatest result over all reachable nodes
    // --------------------------------------------------------
    int end = start;
    for (int i = 0; i < n; i++) {
        if (dp[i] > dp[end])
            end = i;
    }

    cout << "Maximum sum: " << dp[end] << "\n";

    // --------------------------------------------------------
    // Reconstructing the path
    // --------------------------------------------------------
    vector<int> path;
    for (int x = end; x != -1; x = parent[x]) {
        path.push_back(x);
    }
    reverse(path.begin(), path.end());

    cout << "Path: ";
    for (int x : path) cout << x << " ";
    cout << "\n";

    return 0;
}

For the weighted example above (the input: n m start, then the edges a b w):

Input

6 6 0
0 1 5
1 3 2
0 2 3
1 4 7
2 4 1
4 5 4

Output

Maximum sum: 16
Path: 0 1 4 5 

How do we reconstruct the longest path?


So far we have learnt how to compute the length of the longest path in a DAG. However, in practice we often also want to know which nodes make up that path.

That is why, besides the array dp, we introduce another array:


parent[v]

The array parent remembers where we came from to the node v when we found the currently best path.

In other words:


parent[v] = the previous node on the best path to v

When during relaxation we find a better path to some node, we update both dp and parent.


if (dp[v] + 1 > dp[to]) {
    dp[to] = dp[v] + 1;
    parent[to] = v;
}
An important idea:

dp keeps the length of the best path, and parent keeps the information on how to trace that path back.

For example, if after the algorithm finishes we get:


parent[1] = 0
parent[2] = 1
parent[3] = 1
parent[4] = 2
parent[5] = 4

and if node 5 is the end of the longest path, then we do the reconstruction by starting from it and following the parent pointers backwards:


5 → 4 → 2 → 1 → 0

Since the path was obtained backwards, at the end we just reverse the order:


0 → 1 → 2 → 4 → 5

In this way we get the concrete longest path, not only its length.

Going back through the parent pointers from the last to the first node in a DAG
The parent array makes it possible to reconstruct the concrete longest path after the DP algorithm has finished.
When is the parent array needed?

If the task asks only for the length of the path, the dp array is enough. If the task also asks to print the path itself, the parent array is needed as well.

That is why graph DP tasks often use the pattern:


dp[]      → the best result
parent[]  → reconstructing the solution

The same principle is often used in other algorithms too, for example when we want to reconstruct the path after Dijkstra's algorithm.



Explanation of the weighted variant

The idea here is the same, only every edge has its own weight. Since the graph has no cycles, negative weights are not a problem.

When we process a node in topological order, all its predecessors have already been processed, so every attempt at relaxation comes at the right moment.

Important:

We do not use Dijkstra for the longest path in a DAG. Dijkstra is an algorithm for the shortest path, and only under special conditions. Here we need a DAG + topological order + DP.


How do we get the concrete path back?


If we want only the length of the longest path, it is enough to follow the DP values. But if we also want the path itself, we keep the parent of the node from which we last improved the value.

The idea:

Whenever dp[v] becomes larger, we remember parent[v] = u. At the end we start from the last node backwards and get the whole path.

This is the standard reconstruction technique in DP problems.



Common mistakes and traps


One of the most common mistakes is trying to find the longest path in a graph that has a cycle. Then this simple algorithm is no longer enough.

Another common mistake is running the DP without a topological order. Then we can process a node before all its predecessors are ready, and the result becomes wrong.

Tip:

If the graph is not a DAG, you first have to solve the problem of cycles or use a completely different approach.


Practice tasks


It is good to try the longest path from a given starting node first, and then the variant in which the global maximum in the whole DAG is asked for. Those are the two most common forms of this task.

After that, it is interesting to solve problems that model:

the critical path in a project, the durations of activities, task dependencies and the maximum profit through a DAG.

A comparison of a DAG and a directed graph with a cycle
DP in topological order works only in DAGs, without cycles.

Conclusion


The longest path in a DAG is a very nice example of how topological sorting and dynamic programming complement each other perfectly.

The topological order gives the correct order of processing, and DP keeps the best result for every node. That is why the whole problem can be solved in linear time, without checking all the possible paths.

The essence:

In a DAG the longest path is not found by force through all the paths, but by a clever order of processing.

An infographic showing a DAG with the longest path found with topological sorting and dynamic programming. The upper part shows the original directed acyclic graph with several possible paths, while the lower part shows the topological order of the nodes and the computation of the DP values. The longest path is marked in green, and a shorter alternative path in red.
Figure 1: A visual display of the algorithm for finding the longest path in a DAG with topological sorting and dynamic programming. The longest path is marked in green, while a shorter path is shown in red for comparison. The lower part of the picture shows the topological order of processing the nodes and how the DP values are propagated through the graph.

Tasks to solve on your own


Task 1: The longest path from a starting node


A directed acyclic graph (DAG) with N nodes and M edges is given. Every edge has a positive weight.

For a given starting node S, determine the maximum possible sum of the weights of a path that starts at that node. Also print one concrete longest path.

If there are several longest paths, it is enough to print any one of them.

The input: the first line contains N M S, and then M lines follow with the edges a b w (an edge a → b of weight w); the nodes are numbered from 0.

Important:

The graph is a DAG, which means it has no cycles. That is why we can use topological sorting and dynamic programming.

Task 2: The longest path in the whole DAG


A directed acyclic graph (DAG) with N nodes and M edges is given. Every edge has a weight.

Find the length of the longest path in the whole graph, that is, a path that can start and end at any nodes.

It is enough to print only the length of the longest path, without the path itself.

Note:

Here the starting node is not given in advance. That is why every node can be a possible start of the path.

Task 3: The critical path in a project


A big project consists of N activities. Every activity has a certain duration and can start only when all the activities it depends on have finished.

The dependencies between the activities form a directed acyclic graph (DAG), because an activity cannot indirectly depend on itself.

Determine:

The critical path is a sequence of activities whose total duration determines the total duration of the project.


Task 4: The maximum profit through a network of towns


N towns connected by one-way roads are given. Every town has a certain profit that we can make if we visit it.

Movement is allowed only in the direction of the roads, and the graph is guaranteed to be a DAG.

Determine:

When we visit a town, we can take its profit only once.


Check your knowledge

Open the quiz

The longest path in a DAG

1. Why is the longest path in a DAG easy to compute, but not in a general graph?




2. In what order are the nodes processed?




3. How do you get the longest path itself back?