Introduction

The phrase "longest path from a given node" is easy to say but harder to answer precisely, because the right algorithm depends completely on the graph type. In a directed acyclic graph, the problem is solvable exactly in linear time. In a general graph, finding the longest simple path is hard, and for many cases there is no simple efficient exact algorithm. That is why practical solutions often combine exact handling for special cases with heuristics for the general case.

First Ask What Kind of Graph You Have

There are two very different situations:

• if the graph is a DAG, use an exact dynamic-programming solution
• if the graph has cycles and you want a simple path, the problem becomes much harder

This distinction matters more than any implementation detail. Many discussions about "approximation" are really mixing these two cases together.

Exact Solution for a DAG

If the graph is a DAG, you can compute the longest path from a source using topological order.

1from collections import defaultdict, deque
2
3def longest_path_dag(graph, start):
4    indegree = defaultdict(int)
5    for u in graph:
6        for v, _ in graph[u]:
7            indegree[v] += 1
8
9    queue = deque([node for node in graph if indegree[node] == 0])
10    topo = []
11    while queue:
12        u = queue.popleft()
13        topo.append(u)
14        for v, _ in graph[u]:
15            indegree[v] -= 1
16            if indegree[v] == 0:
17                queue.append(v)
18
19    dist = {node: float("-inf") for node in graph}
20    dist[start] = 0
21
22    for u in topo:
23        if dist[u] == float("-inf"):
24            continue
25        for v, w in graph[u]:
26            dist[v] = max(dist[v], dist[u] + w)
27
28    return dist
29
30graph = {
31    "A": [("B", 2), ("C", 3)],
32    "B": [("D", 4)],
33    "C": [("D", 1)],
34    "D": []
35}
36
37print(longest_path_dag(graph, "A"))

In a DAG, this is exact, not approximate.

Why General Graphs Are Hard

In general graphs with cycles, the longest simple path problem is computationally hard. If repeated vertices are allowed and the graph has a positive cycle, the path can grow without bound, so the question itself becomes ill-defined. That is why practical formulations usually require a simple path, meaning no repeated vertices.

Once you add that requirement, exact search often becomes exponential in the worst case.

Practical Heuristic: Depth-First Search With Pruning

If the graph is small enough or moderately constrained, a heuristic or bounded DFS can still be useful.

1def longest_path_heuristic(graph, start):
2    best = []
3
4    def dfs(node, path):
5        nonlocal best
6        if len(path) > len(best):
7            best = path[:]
8
9        for nxt in graph.get(node, []):
10            if nxt not in path:
11                path.append(nxt)
12                dfs(nxt, path)
13                path.pop()
14
15    dfs(start, [start])
16    return best
17
18graph = {
19    "A": ["B", "C"],
20    "B": ["D", "E"],
21    "C": ["F"],
22    "D": [],
23    "E": ["F"],
24    "F": []
25}
26
27print(longest_path_heuristic(graph, "A"))

This is exact on small graphs, but it does not scale well on large dense graphs.

What "Approximation" Usually Means in Practice

In production systems, people often use approximation to mean:

• greedy exploration
• beam search
• repeated randomized DFS
• domain-specific pruning

These do not guarantee the true longest path in arbitrary graphs, but they can produce a useful long path quickly when exact search is too expensive.

The right heuristic depends heavily on graph structure and what kind of error is acceptable.

Choosing the Right Strategy

Use this practical rule:

• DAG: solve exactly
• small cyclic graph: DFS or branch-and-bound may still be fine
• large general graph: use heuristics and accept that optimality may be unavailable

That decision is more important than the specific programming language or data structure you start with.

Common Pitfalls

• Asking for an approximation algorithm before checking whether the graph is actually a DAG.
• Ignoring cycles and accidentally making the longest path question undefined.
• Assuming a shortest-path style algorithm can be inverted to solve longest simple path in general graphs.
• Using exhaustive DFS on large graphs without acknowledging the growth in search space.
• Calling a heuristic "exact" just because it works on small test graphs.

Summary

• The longest-path problem depends critically on whether the graph is acyclic.
• In DAGs, the longest path from a source can be solved exactly and efficiently.
• In general graphs, the longest simple path problem is hard.
• Heuristics such as DFS with pruning can be useful when exact search is too expensive.
• Always define the graph model clearly before choosing an algorithm.