Introduction

If you need all paths from node A to node Z, the standard approach is depth-first search with backtracking. The critical constraint is that "find all paths" can be exponentially expensive in the size of the graph, so the real goal is not to make it magically cheap, but to enumerate paths correctly without doing unnecessary work.

The Core Idea: DFS with Backtracking

For a graph stored as an adjacency list, DFS is the natural fit. You walk forward from the current node, add it to the current path, and backtrack after exploring each branch.

Here is a runnable Python example for all simple paths in a directed graph:

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

This prints every simple path from A to Z without revisiting nodes already in the current path.

Why "Efficient" Has a Hard Limit

There is an important theoretical limit here: if the graph contains many possible paths, the output itself can be enormous. No algorithm can list all paths faster than it takes to emit them.

That means the best practical algorithm is one that:

• avoids duplicate exploration
• avoids cycles in the current path
• uses memory proportional to the current path, not all possible branches at once

DFS with backtracking satisfies those requirements for most cases.

Handling Cycles Correctly

If the graph can contain cycles, you must prevent infinite recursion. The usual rule for "all simple paths" is to maintain a visited set for the current recursion branch only.

That detail matters. A global visited set would be wrong because it would block valid paths that reuse the same node through different branches.

Consider this graph:

1graph = {
2    "A": ["B", "C"],
3    "B": ["C", "Z"],
4    "C": ["B", "Z"],
5    "Z": []
6}

Here, B and C connect to each other. Branch-local tracking prevents the search from bouncing forever while still allowing valid paths such as A -> B -> Z and A -> C -> Z.

If the Graph Is a DAG

When the graph is a directed acyclic graph, the problem becomes simpler because cycles are impossible. DFS still works well, and you can sometimes add memoization for counts or suffixes. But be careful: memoization is much more useful for counting paths than for materializing every path, because storing all suffix-path combinations can still become very large.

If you only need the number of paths, use dynamic programming instead of enumerating them:

1graph = {
2    "A": ["B", "C"],
3    "B": ["Z"],
4    "C": ["Z"],
5    "Z": []
6}
7
8
9def count_paths(graph, node, goal, memo):
10    if node == goal:
11        return 1
12    if node in memo:
13        return memo[node]
14
15    total = 0
16    for neighbor in graph.get(node, []):
17        total += count_paths(graph, neighbor, goal, memo)
18
19    memo[node] = total
20    return total
21
22
23print(count_paths(graph, "A", "Z", {}))

That distinction is important. Counting paths and listing paths are different tasks with different cost profiles.

Practical Optimizations

You can still make DFS more practical:

• stop early if you only need the first k paths
• prune branches using domain rules
• store the graph as an adjacency list
• avoid copying the whole path on every recursive step

In the first example, the code only copies the path when a complete path reaches the goal. During recursion it mutates one list and backtracks, which is much cheaper than allocating a new list at every edge.

Common Pitfalls

The biggest mistake is asking for all paths when what you really need is the shortest path or the path count. If you only need a shortest path, use BFS for unweighted graphs or Dijkstra's algorithm for weighted graphs.

Another mistake is using a global visited set for all DFS branches. That incorrectly suppresses valid paths.

Developers also underestimate the worst-case explosion in path count. Even a modest graph can have an impractically large number of paths, so "efficient" still needs to be evaluated against the required output size.

Finally, avoid representing the graph in a way that makes neighbor lookup expensive. An adjacency list is usually the right default for sparse graphs.

Summary

• To find all simple paths from A to Z, use DFS with backtracking.
• The total number of paths can be exponential, so no algorithm can make full enumeration cheap in the worst case.
• Use branch-local cycle detection instead of one global visited set.
• For DAGs, dynamic programming is excellent for counting paths but does not remove the cost of listing every path.
• Be clear whether you need all paths, the shortest path, or only the path count before choosing the algorithm.