Introduction

If the goal is to find all possible paths from one node to another in a graph, the standard algorithm is depth-first search with backtracking. The main caution is that "all path combinations" can grow exponentially, so the algorithm is conceptually simple but can become very expensive on large or cyclic graphs.

Model the graph clearly

A common representation is an adjacency list. For example:

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

In this graph, the paths from A to D are:

• 'A -> B -> D'
• 'A -> C -> D'

That is exactly the sort of result a backtracking path enumeration algorithm produces.

Depth-first search with backtracking

1def all_paths(graph, start, end, path=None):
2    if path is None:
3        path = []
4
5    path = path + [start]
6
7    if start == end:
8        return [path]
9
10    paths = []
11    for neighbor in graph.get(start, []):
12        if neighbor not in path:
13            paths.extend(all_paths(graph, neighbor, end, path))
14
15    return paths
16
17graph = {
18    "A": ["B", "C"],
19    "B": ["D"],
20    "C": ["D"],
21    "D": []
22}
23
24print(all_paths(graph, "A", "D"))

This recursively explores each branch, records the current path, and backtracks when a branch ends.

Why cycle handling matters

If the graph can contain cycles, you must avoid revisiting nodes already in the current path or the recursion can loop forever.

That is why the example checks:

if neighbor not in path:

For a directed acyclic graph, this is simpler. For a general graph, cycle prevention is essential.

What if you only need the count

Sometimes the real problem is not "list every path" but "count how many paths exist". If that is the case, dynamic programming can be much better on DAGs because you can reuse subproblem results instead of materializing every full path list.

So the correct algorithm depends on the exact requirement:

• list all paths: DFS and backtracking
• count paths in a DAG: dynamic programming can be better
• shortest path: use a shortest-path algorithm instead

These are related graph questions, but they are not the same problem.

Complexity can explode quickly

Even with a correct DFS, enumerating all paths can be expensive because the number of valid paths may itself be huge. No algorithm can avoid the output cost if you truly need to materialize every path.

That is an important reality check. Sometimes the right answer is not a "faster enumeration algorithm" but changing the requirement to counting, pruning, or finding only the best path.

Ordering and pruning are often part of the real solution

In practice, path enumeration problems often come with extra rules such as a maximum path length, a cost threshold, or a requirement to return results in a stable order. Those constraints are useful because they let you prune branches early instead of exploring everything.

1def bounded_paths(graph, start, end, max_depth, path=None):
2    if path is None:
3        path = []
4    path = path + [start]
5
6    if len(path) > max_depth:
7        return []
8    if start == end:
9        return [path]
10
11    result = []
12    for neighbor in sorted(graph.get(start, [])):
13        if neighbor not in path:
14            result.extend(bounded_paths(graph, neighbor, end, max_depth, path))
15    return result

This does not change the basic DFS idea, but it makes the algorithm more practical for real applications.

Common Pitfalls

• Forgetting to prevent cycles and getting infinite recursion or repeated paths.
• Asking for all paths when the real problem only needs a count or the shortest route.
• Blaming the DFS algorithm when the real issue is exponential output size.
• Using a shared mutable path list incorrectly and corrupting the backtracking state.
• Confusing graph path enumeration with shortest-path algorithms like Dijkstra or A*.

Summary

• To list all path combinations between two nodes, use depth-first search with backtracking.
• Represent the graph as an adjacency list for simplicity.
• Prevent revisiting nodes in the current path when cycles are possible.
• If you only need path counts or shortest paths, use a different algorithm.
• The real cost is often the number of valid paths, not the recursion syntax.