Introduction

Finding every path between two graph nodes is useful for dependency analysis, route inspection, and workflow debugging when a single shortest path is not enough. The standard technique is depth-first search with backtracking, but path enumeration can grow explosively, so practical implementations need cycle control and often need limits as well.

Decide What Counts as a Path

Before writing code, define the path semantics clearly:

1. directed or undirected graph
2. simple paths only, or repeated nodes allowed
3. maximum path length, if any

Most implementations enumerate simple paths, meaning a node cannot appear twice in the same candidate path. That avoids infinite loops on cyclic graphs and usually matches what users mean by “all paths.”

Recursive DFS With Backtracking

The clearest implementation uses depth-first search. Keep track of the current path and the nodes visited on the current branch, then backtrack when you return from recursion.

1def all_paths(graph, start, target):
2    results = []
3    path = []
4    visited = set()
5
6    def dfs(node):
7        path.append(node)
8        visited.add(node)
9
10        if node == target:
11            results.append(path.copy())
12        else:
13            for neighbor in graph.get(node, []):
14                if neighbor not in visited:
15                    dfs(neighbor)
16
17        visited.remove(node)
18        path.pop()
19
20    dfs(start)
21    return results
22
23
24graph = {
25    "A": ["B", "C"],
26    "B": ["D"],
27    "C": ["D"],
28    "D": ["E"],
29    "E": [],
30}
31
32print(all_paths(graph, "A", "E"))

This works well for simple path enumeration in a directed graph and is usually the best version to understand first.

Iterative Search Avoids Recursion Limits

If the graph can be deep enough to threaten recursion depth, switch to an explicit stack. The logic stays similar, but the runtime stack is replaced by your own data structure.

1def all_paths_iterative(graph, start, target):
2    results = []
3    stack = [(start, [start])]
4
5    while stack:
6        node, path = stack.pop()
7
8        if node == target:
9            results.append(path)
10            continue
11
12        for neighbor in graph.get(node, []):
13            if neighbor not in path:
14                stack.append((neighbor, path + [neighbor]))
15
16    return results

This form is often easier to instrument with counters, timeouts, or early termination rules.

Add Limits for Real Systems

The number of paths between two nodes can be exponential in the size of the graph. That means “find all paths” is sometimes an impossible request at production scale. If the graph is user-supplied or dense, protect the search with depth and count limits.

1def all_paths_limited(graph, start, target, max_depth=8, max_paths=1000):
2    results = []
3
4    def dfs(node, path):
5        if len(path) > max_depth or len(results) >= max_paths:
6            return
7
8        if node == target:
9            results.append(path.copy())
10            return
11
12        for neighbor in graph.get(node, []):
13            if neighbor not in path:
14                path.append(neighbor)
15                dfs(neighbor, path)
16                path.pop()
17
18    dfs(start, [start])
19    return results

These limits do not change the fundamental complexity, but they keep the query bounded enough to survive in an API or service.

Stream Results Instead of Storing Everything

If the consumer can process paths one at a time, yield them lazily rather than storing every path in memory first.

1def iter_paths(graph, start, target):
2    stack = [(start, [start])]
3
4    while stack:
5        node, path = stack.pop()
6        if node == target:
7            yield path
8            continue
9
10        for neighbor in graph.get(node, []):
11            if neighbor not in path:
12                stack.append((neighbor, path + [neighbor]))

This is useful when the caller only needs the first few paths or wants to stop after inspecting enough evidence.

Test Boundary Cases Explicitly

Graph path code breaks most often on edge conditions. Good tests should cover:

1. no path exists
2. a cycle is present
3. start == target
4. multiple branching routes

Those tests catch missed copy operations, bad cycle checks, and incorrect base cases early.

Common Pitfalls

The main mistake is forgetting to prevent revisiting nodes, which causes infinite traversal on cyclic graphs. Another is storing the mutable path list directly without copying it when a path is found. Teams also underestimate how quickly the number of valid paths can explode, then discover too late that an unbounded all-path query is not safe for production.

Summary

• Use depth-first search with backtracking to enumerate simple paths.
• Add cycle control so graphs with loops do not recurse forever.
• Prefer an iterative stack if recursion depth is a concern.
• Bound search depth or path count in production-facing systems.
• Stream results when possible to reduce memory pressure.