The longest path problem asks for the path with the most edges (or the largest total weight) in a graph. On a directed acyclic graph (DAG) you solve it in O(V + E) with a topological order and a small DP array. On a general graph with cycles it is NP-hard, so no known algorithm is fast on every input. Most interview problems that look like “longest path” are the DAG case in disguise: a grid with increasing values, a course schedule, or a tree.
Why it is harder than shortest path
Shortest path has polynomial algorithms (BFS, Dijkstra, Bellman-Ford). Longest simple path, where no node repeats, is NP-hard on general graphs, because it contains the Hamiltonian path problem: a path through all n nodes exists exactly when the longest simple path has n - 1 edges.
The naive idea of “negate the weights and run shortest path” fails. With cycles you get negative cycles, and the walk can loop forever. Without cycles, the idea works, but you don’t need it: a DAG has a much simpler solution.
Longest path in a DAG
In a DAG every edge goes “forward” in some ordering of the nodes (a topological order). So if you process nodes in that order, by the time you reach a node all the paths that can end at it are already accounted for. Define dist[v] as the number of edges on the longest path that ends at v. Start every node at 0 and relax each edge u -> v with dist[v] = max(dist[v], dist[u] + 1). The answer is the largest value in dist.
Kahn’s algorithm (repeatedly remove nodes with in-degree 0) gives the topological order and does the DP in one pass. It has a bonus: if fewer than n nodes get processed, the graph has a cycle, so you can reject invalid input instead of returning a wrong answer.
from collections import deque
def longest_path_dag(n, edges):
"""Number of edges on the longest path in a DAG with nodes 0..n-1.
Returns -1 if the graph has a cycle."""
if n == 0:
return 0
graph = [[] for _ in range(n)]
indegree = [0] * n
for u, v in edges:
graph[u].append(v)
indegree[v] += 1
queue = deque(i for i in range(n) if indegree[i] == 0)
dist = [0] * n # dist[v] = longest path (in edges) ending at v
processed = 0
while queue:
u = queue.popleft()
processed += 1
for v in graph[u]:
dist[v] = max(dist[v], dist[u] + 1)
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
if processed < n:
return -1
return max(dist)
print(longest_path_dag(6, [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)])) # 3
print(longest_path_dag(3, [])) # 0
print(longest_path_dag(3, [(0, 1), (1, 2), (2, 0)])) # -1
print(longest_path_dag(4, [(0, 1), (2, 3)])) # 1
These print 3, 0, -1 and 1. In the first graph the longest path is 0 -> 1 -> 3 -> 4, with 3 edges. The last graph is disconnected, and the answer is still correct because every in-degree-0 node starts the queue.
Complexity
Time is O(V + E): each node enters the queue once and each edge is relaxed once. Space is O(V + E) for the adjacency list plus O(V) for the in-degree, distance and queue arrays.
Memoized DFS version
You can get the same result top-down: the longest path starting at u is 0 if u has no outgoing edges, otherwise 1 plus the best of its neighbors. Cache the result per node. This is the form to reach for when the graph is implicit, as in grid problems. Python’s default recursion limit is about 1000 frames, so a long chain of nodes needs an iterative version (like Kahn’s above) or a raised limit.
from functools import lru_cache
def longest_dfs(n, edges):
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
@lru_cache(None)
def f(u):
return max((f(v) + 1 for v in g[u]), default=0)
return max((f(i) for i in range(n)), default=0)
print(longest_dfs(6, [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)])) # 3
This version assumes the graph is acyclic. On a cycle it recurses without end, so check for cycles first if the input is not guaranteed to be a DAG (see detecting cycles in graphs).
Nodes or edges? Read the statement
The most common wrong answer is off by one. A path with k nodes has k - 1 edges, and problems differ on which they ask for. A single node is a path of length 0 in edges and 1 in nodes. Check this against the examples before you code. Also decide up front what an empty graph returns; the code above returns 0.
The same idea with weights: Parallel Courses III
When nodes or edges carry weights, you add the weight instead of 1. LeetCode 2050, Parallel Courses III, is the standard example: each course has a duration in months, prerequisites form a DAG, you can take any number of courses in parallel, and you need the minimum total time. That time is the longest weighted path through the prerequisite graph. Here finish[c] is the earliest month by which course c can be finished.
from collections import deque
def minimum_time(n, relations, time):
graph = [[] for _ in range(n + 1)]
indegree = [0] * (n + 1)
for a, b in relations: # a must finish before b starts
graph[a].append(b)
indegree[b] += 1
finish = [0] * (n + 1)
queue = deque()
for c in range(1, n + 1):
finish[c] = time[c - 1]
if indegree[c] == 0:
queue.append(c)
while queue:
u = queue.popleft()
for v in graph[u]:
finish[v] = max(finish[v], finish[u] + time[v - 1])
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
return max(finish)
print(minimum_time(3, [[1, 3], [2, 3]], [3, 2, 5])) # 8
print(minimum_time(5, [[1, 5], [2, 5], [3, 5], [3, 4], [4, 5]], [1, 2, 3, 4, 5])) # 12
This is also how the critical path in project scheduling is computed, and the same shape appears in build systems: the longest dependency chain sets the minimum build time even with unlimited parallel workers.
LeetCode problems that are longest path in disguise
- 329. Longest Increasing Path in a Matrix. Cells are nodes, with an edge to a neighbor that has a larger value. Strictly increasing values mean no cycles, so it is a DAG and memoized DFS is O(m * n).
- 543. Diameter of Binary Tree. The longest path between any two nodes in a tree, counted in edges. It does not have to pass through the root.
- 2050. Parallel Courses III. Weighted longest path in a DAG, shown above.
- 1857. Largest Color Value in a Directed Graph. Topological order with a DP table per node and color, and a cycle check that returns -1.
Tree diameter
For each node, the longest path that bends at it is left_depth + right_depth. Return the depth upward and keep the best bend seen so far.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val, self.left, self.right = val, left, right
def diameter(root):
best = 0
def depth(node):
nonlocal best
if not node:
return 0
l, r = depth(node.left), depth(node.right)
best = max(best, l + r)
return 1 + max(l, r)
depth(root)
return best
t = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(diameter(t)) # 3 (4 -> 2 -> 1 -> 3, or 5 -> 2 -> 1 -> 3)
To practice this one step by step, there is a Binary Tree Diameter lesson on AlgoCademy.
Longest increasing path in a matrix
def longest_increasing_path(matrix):
if not matrix or not matrix[0]:
return 0
m, n = len(matrix), len(matrix[0])
memo = {}
def dfs(i, j):
if (i, j) in memo:
return memo[(i, j)]
best = 1 # the cell itself
for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
x, y = i + di, j + dj
if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
best = max(best, 1 + dfs(x, y))
memo[(i, j)] = best
return best
return max(dfs(i, j) for i in range(m) for j in range(n))
print(longest_increasing_path([[9, 9, 4], [6, 6, 8], [2, 1, 1]])) # 4
print(longest_increasing_path([[3, 4, 5], [3, 2, 6], [2, 2, 1]])) # 4
Both grids give 4 (the first is 1 -> 2 -> 6 -> 9). Without the memo the DFS re-explores the same cells exponentially often; with it, each cell is computed once. If memoization is new to you, see tabulation and memoization or the Memoization lesson. A closely related write-up is longest path in a DAG.
Common mistakes
- Running the DAG algorithm on a graph with cycles. Kahn’s version detects it; plain DFS recursion does not.
- Marking nodes visited and never revisiting them in a longest-path DFS. A visited set is right for reachability, not for longest path; use a memo of results instead, which is only valid on a DAG.
- Mixing up nodes and edges in the final answer, as described above.
- Forgetting disconnected parts. Start from every node with in-degree 0 (Kahn) or loop over all start nodes (DFS).
- Recursion depth. A path graph with 100,000 nodes breaks recursive DFS in Python; use the iterative version.
If the graph has cycles
If the problem allows cycles and wants a simple path, you are in NP-hard territory. In an interview that means one of three things: the input is small enough for backtracking (exponential, with a visited set that you undo), the graph has extra structure (a tree, a DAG, a bitmask DP over at most about 20 nodes), or you misread the problem. Say so out loud, and ask about constraints before choosing an approach.
For more graph practice, AlgoCademy has a Graphs section with guided problems, including DFS and BFS exercises, in its Python course.
