Introduction

Enumerating all possible paths in a graph is a classic graph-search problem with applications in routing, puzzle solving, static analysis, and workflow exploration. The hard part is not writing one traversal, but choosing the right notion of “path,” avoiding infinite loops, and understanding that the number of paths can grow exponentially even on modest graphs.

Define What Counts as a Path

Before choosing an algorithm, be explicit about the problem:

• Are you enumerating all simple paths between two nodes?
• Are repeated vertices allowed?
• Is the graph directed or undirected?
• Do you want paths from one source to one destination or all sources to all destinations?

If cycles are allowed and repeated vertices are permitted, “all possible paths” may be infinite. In most practical settings, the intended problem is to enumerate all simple paths, meaning paths that do not repeat vertices.

Depth-First Search with Backtracking

The standard approach for enumerating all simple paths from a source to a destination is depth-first search with backtracking.

1from collections import defaultdict
2
3graph = {
4    "A": ["B", "C"],
5    "B": ["C", "D"],
6    "C": ["D"],
7    "D": []
8}
9
10def all_paths(graph, start, end):
11    path = []
12    result = []
13
14    def dfs(node):
15        path.append(node)
16
17        if node == end:
18            result.append(path.copy())
19        else:
20            for neighbor in graph.get(node, []):
21                if neighbor not in path:
22                    dfs(neighbor)
23
24        path.pop()
25
26    dfs(start)
27    return result
28
29print(all_paths(graph, "A", "D"))

This works well because the current path doubles as the visited set for simple-path enumeration.

Use a Separate Visited Set for Clarity

If membership checks in the path list feel too implicit, use a dedicated visited set.

1def all_paths_with_visited(graph, start, end):
2    path = []
3    visited = set()
4    result = []
5
6    def dfs(node):
7        path.append(node)
8        visited.add(node)
9
10        if node == end:
11            result.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 result

This version can be easier to maintain when the path object and the visitation logic need to evolve separately.

Enumerate Paths Lazily with a Generator

If the graph may produce many paths, yielding them one at a time is often better than collecting them all into memory.

1def iter_paths(graph, start, end, path=None):
2    if path is None:
3        path = []
4
5    path = path + [start]
6
7    if start == end:
8        yield path
9        return
10
11    for neighbor in graph.get(start, []):
12        if neighbor not in path:
13            yield from iter_paths(graph, neighbor, end, path)
14
15
16for p in iter_paths(graph, "A", "D"):
17    print(p)

This does not change the worst-case time complexity, but it reduces peak memory when you want to process paths incrementally.

Complexity and Practical Limits

Path enumeration is often expensive because the number of simple paths can be exponential in the size of the graph. That means the question is not only “what algorithm should I use,” but also “can I afford to enumerate them at all.”

Practical constraints often help:

• maximum path length
• stop after the first k paths
• only accept paths satisfying a predicate

Adding those constraints can turn an otherwise explosive search into something operationally manageable.

Directed Versus Undirected Graphs

In an undirected graph, every edge is usually available both ways, which increases the risk of accidental backtracking loops if you do not enforce simple-path rules carefully.

Example undirected representation:

1graph = {
2    1: [2, 3],
3    2: [1, 4],
4    3: [1, 4],
5    4: [2, 3],
6}

The same DFS pattern works, but cycle prevention becomes even more important because every edge can immediately lead back to the previous node.

When Not to Enumerate All Paths

If your real goal is shortest path, reachability, or path count only, enumerating every path is usually the wrong tool.

Use:

• BFS for shortest paths in unweighted graphs
• Dijkstra or A* for weighted shortest paths
• dynamic programming for counting paths in DAGs

Full enumeration is the right tool only when you genuinely need the paths themselves.

Common Pitfalls

The biggest mistake is asking for “all paths” on a cyclic graph without defining whether repeated vertices are allowed. That can make the search infinite.

Another issue is collecting every path into memory when a generator would allow incremental processing.

People also use enumeration when they only needed the shortest path or path count, which makes the solution much more expensive than necessary.

Summary

• Most practical path-enumeration problems mean all simple paths, not arbitrary repeated-vertex walks.
• Depth-first search with backtracking is the standard solution.
• Use generators when the result set may be large.
• Expect exponential growth in the number of paths on nontrivial graphs.
• Do not enumerate every path if the real goal is shortest path, reachability, or count only.