Introduction

For a directed acyclic graph, the maximum-path problem is much easier than in a general directed graph because there are no cycles to create infinite walks or revisitation complexity. The standard solution is dynamic programming over a topological order, which gives a linear-time algorithm in the size of the graph.

Decide What “Maximum Path” Means

Before writing code, pin down the objective. In a DAG, “maximum path” usually means one of these:

• the path with the maximum total edge weight
• the path with the maximum total node weight
• the longest path by number of edges when all edges have weight 1

The algorithmic pattern is the same in all three cases. Process nodes in topological order and relax outgoing edges using max instead of min.

Why Topological Order Solves It

A topological ordering lists every vertex so that all edges point forward in the order. Because the graph is acyclic, such an order always exists.

That property makes dynamic programming possible. By the time you process a node, every predecessor that could improve its score has already been processed. So you can compute the best path ending at each node with one forward pass.

Weighted Longest Path Algorithm

Assume the graph is stored as an adjacency list where each edge is (neighbor, weight). The recurrence is:

dist[v] = max(dist[v], dist[u] + weight(u, v))

Here is a runnable Python implementation that returns both the maximum score and one optimal path.

1from collections import deque
2
3
4def longest_path_dag(graph):
5    nodes = set(graph)
6    for u in graph:
7        for v, _ in graph[u]:
8            nodes.add(v)
9
10    indegree = {u: 0 for u in nodes}
11    for u in graph:
12        for v, _ in graph[u]:
13            indegree[v] += 1
14
15    topo_queue = deque([u for u in nodes if indegree[u] == 0])
16    topo = []
17
18    while topo_queue:
19        u = topo_queue.popleft()
20        topo.append(u)
21        for v, _ in graph.get(u, []):
22            indegree[v] -= 1
23            if indegree[v] == 0:
24                topo_queue.append(v)
25
26    dist = {u: float("-inf") for u in nodes}
27    prev = {u: None for u in nodes}
28
29    for u in topo:
30        if dist[u] == float("-inf"):
31            dist[u] = 0
32        for v, w in graph.get(u, []):
33            if dist[u] + w > dist[v]:
34                dist[v] = dist[u] + w
35                prev[v] = u
36
37    end = max(dist, key=dist.get)
38    path = []
39    while end is not None:
40        path.append(end)
41        end = prev[end]
42    path.reverse()
43
44    return max(dist.values()), path
45
46
47graph = {
48    "A": [("B", 5), ("D", 3)],
49    "B": [("C", 7)],
50    "C": [("E", 1)],
51    "D": [("E", 8)],
52    "E": [],
53}
54
55score, path = longest_path_dag(graph)
56print(score)
57print(path)

Output:

13
['A', 'B', 'C', 'E']

That path has weight 5 + 7 + 1 = 13, which beats A -> D -> E with weight 11.

Why This Is Efficient

Each node is processed once in topological order, and each edge is relaxed once. That gives time complexity O(V + E), which is one of the big advantages of DAGs.

If the graph were not acyclic, longest-path problems become much harder in general. The DAG property is exactly what makes this dynamic programming approach safe and efficient.

Variations

If all edges have weight 1, the same method finds the longest path by edge count. If you want node weights instead, initialize each node with its own weight and update the recurrence accordingly.

If you need the longest path from one specific source rather than the best path anywhere in the DAG, initialize only that source with 0 and leave every other node at negative infinity.

Common Pitfalls

The most common mistake is trying to use Dijkstra's algorithm for a maximum-path problem. Dijkstra solves a shortest-path problem under different assumptions and is not the right tool here.

Another mistake is forgetting to define the starting condition. If you want the best path anywhere in the DAG, every source node may need to start with score 0. If you want a path from one chosen node, only that node should start at 0.

It is also easy to store only the best distances and forget the predecessor links. If you want the actual path and not just the score, keep a prev map for reconstruction.

Summary

• In a DAG, maximum-path problems are solved efficiently with topological order and dynamic programming.
• Relax edges with max rather than min.
• The weighted version runs in O(V + E) time.
• Store predecessor information if you need the actual path, not just its score.
• Be explicit about whether the path may start anywhere or must start from a specific source.