Longest path in a DAG by topological DP in Python

Why this matters

A building project is a set of tasks, and some tasks must wait for others. The foundation must be dug before the frame goes up. The frame must be up before the wiring goes in. Each task takes some days. The whole project cannot finish before the longest chain of tasks that must run one after another is done. That chain is called the critical path. Finding it is a longest path problem on a graph.

A graph is a set of points joined by arrows. This lesson uses a special kind called a directed acyclic graph, or DAG. "Directed" means every arrow points one way. "Acyclic" means there is no cycle, which is a route that follows the arrows and comes back to where it started. A project plan is a DAG when no task has to wait for itself, directly or through other tasks.

The method is dynamic programming (DP). DP solves small questions, writes each answer in a table, and reuses the table for bigger questions. Here the table has one number for each vertex: the length of the longest path found so far to that vertex. The key is the order in which the vertices are visited. If each vertex is handled only after every arrow into it has been handled, each arrow is looked at once and every number in the table is final at the end. That order is called a topological order.

Earlier lessons in this module used the same table idea on grids and on sequences. The grid version of a path question for minimum sums is in Minimum path sum and triangle from the bottom. This lesson works on any DAG, not only grids.

Words you need first

A vertex is a point in the graph. In the building example a vertex is a milestone, such as "foundation done". Vertices get numbers 0, 1, 2, and so on. Python lists also count from 0, so a graph with 7 vertices uses the numbers 0 to 6.

An edge is an arrow from one vertex to another. An edge from 0 to 2 with weight 3 means "a task that takes 3 days leads from milestone 0 to milestone 2".

The weight is the number on an edge. Here it is a number of days.

A path is a list of vertices where each vertex has an edge to the next one. The length of a path is the total of its edge weights.

A topological order is a list of all the vertices where every edge goes from a vertex that appears earlier in the list to one that appears later. A graph has a topological order exactly when it is a DAG.

To relax an edge means this. You have a known path to the vertex u, and an edge from u to v. Walk along the edge and see whether the new path to v is longer than the best one you already have for v. If it is, record the new, longer path. The word comes from textbooks, and it means "update the table for this edge".

The in-degree of a vertex is the number of arrows that point into it. A vertex with in-degree 0 has no unfinished task before it.

In Python you will see four things in the code. A NamedTuple (from the typing module) is a small class that only holds data. Edge(2, 4) makes an edge to vertex 2 with weight 4, and e.to and e.weight read its two fields. A deque (from the collections module) is a queue: append adds at the back and popleft takes from the front. A list of lists has one entry per vertex, so graph[u] is the list of outgoing edges of vertex u. The value None means "no value". This lesson uses it for "no path found yet".

Readers who know Java: None plays the role that Integer.MIN_VALUE played in the Java version of this lesson. The difference is that Python stops with an error when you do arithmetic on None, so a missing check shows up at once.

The example: a house built in order

Here are the milestones and their vertex numbers. The numbers are arbitrary labels. They are not in order of time.

The edges and their days are:

• 0 -> 2, 3 days (dig the foundation)
• 2 -> 3, 4 days (build the frame)
• 3 -> 4, 2 days (put the roof on)
• 3 -> 5, 3 days (run the wiring)
• 5 -> 6, 2 days (paint the walls after the wiring is in)
• 4 -> 1, 0 days (the roof is the last step on that route)
• 6 -> 1, 0 days (the painting is the last step on that route)

The question is how many days pass before the house is ready. The house is ready only when every route into vertex 1 has finished. So the answer is the longest route.

There are two routes into vertex 1. The first goes 0, 2, 3, 4, 1. It takes 3 + 4 + 2 + 0 = 9 days. The second goes 0, 2, 3, 5, 6, 1. It takes 3 + 4 + 3 + 2 + 0 = 12 days. The longest route gives 12 days, so the house is ready after 12 days.

Notice that the vertex numbers do not follow the order of the work. The edge 4 -> 1 goes from a higher number to a lower one. If you handled the vertices in number order, you would reach vertex 1 too early. The next section fixes that.

Step 1: put the vertices in topological order

The usual method is often called Kahn's algorithm. It works like this.

1. Count the in-degree of every vertex.
2. Put every vertex with in-degree 0 into a queue.
3. Take a vertex from the front of the queue and add it to the order. For each of its outgoing edges, lower the in-degree of the target by 1. If a target's in-degree becomes 0, add it to the back of the queue.
4. Stop when the queue is empty. If the order holds fewer vertices than the graph, the missing vertices are on a cycle.

Here is the core of the method in Python. It assumes the indegree list is already filled in.

ready = deque(v for v in range(n) if indegree[v] == 0)
order = []
while ready:
    u = ready.popleft()
    order.append(u)
    for e in graph[u]:
        indegree[e.to] -= 1
        if indegree[e.to] == 0:
            ready.append(e.to)

Trace it on the house example. The in-degrees are: vertex 0 has 0, vertex 1 has 2 (from 4 and from 6), and vertices 2, 3, 4, 5 and 6 each have 1.

• The queue starts with [0]. Take 0. The order is [0]. The edge 0 -> 2 makes the in-degree of 2 equal to 0, so the queue is [2].
• Take 2. The order is [0, 2]. The edge 2 -> 3 makes 3 ready. The queue is [3].
• Take 3. The order is [0, 2, 3]. Its edges make 4 and 5 ready. The queue is [4, 5].
• Take 4. The order is [0, 2, 3, 4]. The edge 4 -> 1 lowers the in-degree of 1 from 2 to 1. The queue is [5].
• Take 5. The order is [0, 2, 3, 4, 5]. The edge 5 -> 6 makes 6 ready. The queue is [6].
• Take 6. The order is [0, 2, 3, 4, 5, 6]. The edge 6 -> 1 makes 1 ready. The queue is [1].
• Take 1. The order is [0, 2, 3, 4, 5, 6, 1].

A vertex enters the queue only after every arrow into it has been processed. That is why every vertex in the final order comes after all of its predecessors.

Step 2: relax each edge once

Keep two lists. The list dist holds the longest known path length to each vertex. The list parent holds, for each vertex, the vertex just before it on that path, so you can rebuild the path later.

Set dist[start] to 0. Set every other entry to None, which means "no path found yet". Any whole number can be a real length when weights are negative, so no number is safe to use as a marker. None cannot be confused with a real length, and a comparison with it fails loudly instead of quietly giving a wrong answer.

Then walk the vertices in topological order. For each vertex u that has a known distance, look at each outgoing edge u -> v with weight w. The candidate length to v is dist[u] + w. If the candidate is larger than dist[v], store it, and set parent[v] = u.

for u in order:
    if dist[u] is None:
        continue
    for e in graph[u]:
        candidate = dist[u] + e.weight
        if dist[e.to] is None or candidate > dist[e.to]:
            dist[e.to] = candidate
            parent[e.to] = u

The check dist[e.to] is None comes before the comparison, because candidate > None raises a TypeError in Python.

Why is one pass enough? When the loop reaches vertex u, every arrow into u comes from a vertex that appears earlier in the order. Those vertices were already handled, so dist[u] already holds its final value. Nothing later can make it longer, because every later vertex comes after u and has no arrow back to u.

Trace the house example. Each line shows the vertex being handled and the values it changes.

• Start: dist[0] = 0.
• Vertex 0 (distance 0): edge 0 -> 2 gives dist[2] = 3.
• Vertex 2 (distance 3): edge 2 -> 3 gives dist[3] = 7.
• Vertex 3 (distance 7): edge 3 -> 4 gives dist[4] = 9. Edge 3 -> 5 gives dist[5] = 10.
• Vertex 4 (distance 9): edge 4 -> 1 gives dist[1] = 9, with parent 4.
• Vertex 5 (distance 10): edge 5 -> 6 gives dist[6] = 12.
• Vertex 6 (distance 12): edge 6 -> 1 gives the candidate 12. That is larger than the stored 9, so dist[1] = 12, with parent 6.
• Vertex 1 (distance 12): it has no outgoing edges.

The final distances are 0 for vertex 0, 12 for vertex 1, 3 for vertex 2, 7 for vertex 3, 9 for vertex 4, 10 for vertex 5 and 12 for vertex 6. Vertex 1 was written twice. The second write won because 12 is larger than 9.

Step 3: read the answer and the path

The answer is dist[1], which is 12 days. To find the route, start at the target and follow parent back until you reach a vertex whose parent is None. The start has parent None because nothing comes before it. Then reverse the list.

def path_to(parent, target):
    path = []
    v = target
    while v is not None:
        path.append(v)
        v = parent[v]
    path.reverse()
    return path

For vertex 1 the parents are 1 from 6, 6 from 5, 5 from 3, 3 from 2, and 2 from 0. The path is [0, 2, 3, 5, 6, 1]. In words: dig the foundation, build the frame, run the wiring, paint the walls, and the house is ready.

path.reverse() changes the list itself. path[::-1] would give a reversed copy and leave path alone. Both give the same result here.

Worked example: the full program

This program builds the graph, orders it, runs the relaxation from vertex 0, prints the distances, and prints the path. It also runs a second version that starts from any vertex.

The output is:

topological order: [0, 2, 3, 4, 5, 6, 1]
days from start to each milestone:
  0: 0
  1: 12
  2: 3
  3: 7
  4: 9
  5: 10
  6: 12
path to house ready: [0, 2, 3, 5, 6, 1]
longest path ending at each milestone, from any start:
  [0, 12, 3, 7, 9, 10, 12]

The order and distances match the hand trace. The program has one function per idea: topological_order does step 1, relax does step 2, and path_to does step 3. The function longest_from_source fills the lists for a fixed start. The function longest_from_anywhere is the next section.

Each vertex and each edge is handled once. The work is about the number of vertices plus the number of edges, which is written O(V + E). This notation says the work grows in step with the number of vertices plus the number of edges. Kahn's method also makes one pass over the edges.

A second example: the longest path that ends at each vertex

Sometimes there is no single start. You want, for each milestone, the longest chain of work that ends there, starting from any milestone. The change is small. Every vertex starts at 0, which means "a path of length 0 that uses only this vertex". Then relax the same way.

dist = [0] * n    # every entry starts at 0, a path of length 0 with one vertex
parent = [None] * n
relax(graph, topological_order(graph), dist, parent)

The result is [0, 12, 3, 7, 9, 10, 12], as the full program printed. Vertex 2 has value 3 because the best chain ending there starts at 0 and takes 3 days. Vertex 0 has value 0 because no chain of work leads into it. Here the None check does nothing, because no entry is ever None. The rest of the function is unchanged.

A third example: a grid is a DAG

A grid of numbers is also a DAG. Suppose each cell holds some coins, and you may move only right or down. You start at the top-left cell and want the most coins you can collect when you reach the bottom-right cell.

Give each cell a vertex number: cell = row * columns + column. Add an edge from each cell to the cell on its right and to the cell below it. The weight of the edge is the number of coins in the cell it enters.

cell = r * cols + c
if c + 1 < cols:
    graph[cell].append(Edge(cell + 1, coins[r][c + 1]))
if r + 1 < rows:
    graph[cell].append(Edge(cell + cols, coins[r + 1][c]))

Every move goes right or down, so every edge leads to a higher number. The row-by-row order, 0, 1, 2 and so on, is already a topological order, so this grid needs no sorting step. Set dist[0] to the coins in the top-left cell and run the same relaxation loop.

Here is the grid used in the run:

3 1 2
4 9 1

The program below builds the graph from this grid and runs the relaxation loop.

The output is:

most coins to the bottom-right corner: 17

The best route goes down, right, right. It collects 3 + 4 + 9 + 1 = 17 coins. The route that goes right first collects only 3 + 1 + 2 + 1 = 7 coins, so the order of moves matters, and the table finds the better route without trying every one.

Common mistakes

Handling the vertices in number order. This is the most common error. The loop for u in range(n): looks natural, but it works only when every edge points from a lower number to a higher number. Here is a four-vertex graph with the edges 0 -> 2 of weight 4, 2 -> 1 of weight 4, 1 -> 3 of weight 1, and 0 -> 3 of weight 0. The correct longest path to vertex 3 is 0 -> 2 -> 1 -> 3, with length 9. The program below runs the same relaxation twice, first in number order and then in topological order.

The output is:

wrong order (by index): [0, 8, 4, 0]
topological order:      [0, 8, 4, 9]

The first line gives 0 for vertex 3, and the second gives the correct 9. Vertex 1 is handled before vertex 2 has passed its value on. When the loop reaches vertex 1 its distance is still unknown, so the edge 1 -> 3 is skipped. Vertex 3 keeps the value 0 from the direct edge 0 -> 3, and the answer is wrong without any error message. The fix is to build the order first and relax in that order.

Skipping the unknown check. The line if dist[u] is None: continue looks optional. Without it, the loop computes None + weight for an unknown vertex, and Python stops with an error:

The output is:

Traceback (most recent call last):
  File "...", line 2, in <module>
    candidate = unknown + (-1)
                ~~~~~~~~^~~~~~
TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'

The file name and line numbers in the traceback depend on where the file is saved, so the lines that start with File are shortened here. The last line is the exact message. Python gives an error here instead of a wrong answer, and the program stops. The check is still needed, because the program cannot finish without it.

Using 0 for "unknown" when you start from one vertex. Suppose you filled dist with 0 instead of None. Then a vertex that no path reaches still holds 0, which looks like a real path of length 0. Its outgoing edges then produce candidate lengths that were never achieved. The marker must be a value that no real path can have, and None is the safest choice in Python. The debugging lab in the next lesson covers this kind of bug in more detail.

Running on a graph with a cycle. The method needs a DAG. If there is a cycle, some vertices never reach in-degree 0, so the order is incomplete. The program below has the cycle 1 -> 2 -> 1, and the code raises an error with a clear message.

The output is:

Traceback (most recent call last):
  File "...", line 35, in <module>
    topological_order(graph)
    ~~~~~~~~~~~~~~~~~^^^^^^^
  File "...", line 26, in topological_order
    raise ValueError("graph has a cycle")
ValueError: graph has a cycle

As above, the file name and line numbers depend on where the file is saved. The error is the right outcome. A cycle with positive weights makes the longest path infinite, because a route can go around the loop again and again and gain length each time. So the program stops rather than give a wrong answer.

Reading the path from an unreached vertex. path_to follows parents until it reaches None. If the target was never reached, its parent is still None, and the function returns a list with only the target in it. Check the distance first. If it is None, there is no path.

Using < where > is needed. The code above finds the longest path because it keeps a candidate only when it is larger. To find the shortest path you would reverse the comparison and start from a large marker instead of a small one, such as float("inf"). Mixing the two produces answers that look plausible but are wrong.

Practice

Exercise 1. The graph has vertices 0 to 3 and these edges: 0 -> 1 with weight 5, 0 -> 2 with weight 2, 2 -> 1 with weight 6, and 1 -> 3 with weight 1. Find the topological order, the longest path from 0 to 3, and its length.

Show the answer

One valid topological order is 0, 2, 1, 3. The distances are 0 for vertex 0, 2 for vertex 2, 8 for vertex 1 (through vertex 2, since 2 + 6 = 8 is larger than 5), and 9 for vertex 3. The longest path is 0, 2, 1, 3 with length 9.

Exercise 2. The graph has vertices 0 to 4 and these edges: 4 -> 0, 4 -> 1, 3 -> 1 and 1 -> 2. Give one topological order.

Show the answer

Vertices 3 and 4 have in-degree 0, so they come first. One valid order is 3, 4, 0, 1, 2. Another valid order is 4, 3, 0, 1, 2. Any order where every edge's first vertex comes before its second vertex is correct.

Exercise 3. Explain why the method fails on a graph with a cycle of two vertices, 0 -> 1 with weight 1 and 1 -> 0 with weight 1.

Show the answer

Starting at 0, you can go to 1 and back to 0, which adds 2 to the length. You can repeat this as often as you like, so the longest path has no upper limit. The method has no answer to return in that case, so it reports the cycle instead.

Exercise 4. Five courses A, B, C, D and E have these rules: A must come before B and C, both B and C must come before D, and D must come before E. Each course takes one semester, and a student can take any number of courses in a semester. What is the fewest semesters needed to finish all five?

Show the answer

Turn each rule into an edge of weight 1: A -> B, A -> C, B -> D, C -> D and D -> E. The longest path from A to E is A, B, D, E. It has three edges and four courses, and the four courses must run one after another, so it needs four semesters. The answer is 4.

Exercise 5. A student wrote this loop. The dist list was filled with None and only the start vertex was set. The loop is run on the graph from Exercise 1, with order equal to [0, 2, 1, 3]. What is the bug, and how do you fix it?

for u in order:
    for e in graph[u]:
        candidate = dist[u] + e.weight
        if candidate > dist[e.to]:
            dist[e.to] = candidate

Show the answer

The loop has no check for an unknown target. The first edge is 0 -> 1, and dist[1] is still None, so the comparison candidate > dist[e.to] raises TypeError: '>' not supported between instances of 'int' and 'NoneType'. The fix is to check dist[e.to] is None or before the comparison. The line if dist[u] is None: continue is also useful for vertices with no path yet, but it does not stop this error.

Summary

• A DAG has no cycles, so its vertices can be put in a topological order where every edge points forward.
• Kahn's method builds that order from in-degree counts and a queue, and it reports a cycle when some vertices never reach in-degree 0.
• Relaxing each edge once in topological order gives the final longest distances in time proportional to the number of vertices plus the number of edges.
• Keep a parent for each vertex, and rebuild the path by following parents back from the target.
• Use None for unknown vertices, check for None before any comparison or addition, and skip unknown vertices during relaxation.
• Use a greater-than comparison for longest paths. The order of the vertices must come from the topological sort, not from their numbers.