Introduction

In an unweighted undirected graph, the shortest path between two nodes is the path with the fewest edges. If you need all shortest paths rather than just one, the usual solution is breadth-first search to compute distances plus a predecessor map, followed by backtracking to reconstruct every shortest route.

Why BFS Is the Right Starting Point

Because every edge has equal weight, BFS explores the graph in layers of increasing distance from the source. The first time a node is reached, you know its shortest distance. If the same node is reached again at the same shortest distance, that alternative predecessor also belongs to a shortest path.

That is the key idea: do not store only one parent per node. Store all parents that can reach the node with the same minimum distance.

Build Distance and Parent Lists

The algorithm has two phases:

1. run BFS from the source
2. backtrack from the target through all recorded parents

Here is a complete Python example.

1from collections import deque, defaultdict
2
3
4def all_shortest_paths(graph, source, target):
5    distance = {source: 0}
6    parents = defaultdict(list)
7    queue = deque([source])
8
9    while queue:
10        node = queue.popleft()
11
12        for neighbor in graph[node]:
13            if neighbor not in distance:
14                distance[neighbor] = distance[node] + 1
15                parents[neighbor].append(node)
16                queue.append(neighbor)
17            elif distance[neighbor] == distance[node] + 1:
18                parents[neighbor].append(node)
19
20    if target not in distance:
21        return []
22
23    paths = []
24
25    def build(path_node, suffix):
26        if path_node == source:
27            paths.append([source] + suffix)
28            return
29        for parent in parents[path_node]:
30            build(parent, [path_node] + suffix)
31
32    build(target, [])
33    return paths
34
35
36graph = {
37    "A": ["B", "C"],
38    "B": ["A", "D", "E"],
39    "C": ["A", "D", "E"],
40    "D": ["B", "C", "F"],
41    "E": ["B", "C", "F"],
42    "F": ["D", "E"],
43}
44
45for path in all_shortest_paths(graph, "A", "F"):
46    print(path)

For this graph, the output contains every shortest route from A to F.

Why This Works

BFS guarantees shortest distances in unweighted graphs. If a node v is discovered from u, then distance[v] is distance[u] + 1. If another node reaches v with exactly the same shortest value, that second route is also part of a shortest path and must be kept.

That is why the parent structure is a map from node to list of parents rather than node to single parent.

Then the reconstruction phase walks backward from the target to the source, exploring every parent combination. Because all parents obey the shortest-distance rule, every reconstructed path is guaranteed to be shortest.

Complexity

The BFS itself is still O(V + E), where V is the number of vertices and E is the number of edges. The expensive part is output size. If the graph contains many shortest paths, you have to list them all, and that output can be large.

So the practical cost is:

• BFS cost for discovering distances and parents
• plus the cost of generating however many shortest paths actually exist

That means the problem is easy when you need one shortest path, but potentially large when you truly need all of them.

When This Is Better Than Repeated Searches

A common mistake is to run BFS repeatedly and try to "find another shortest path" each time by blocking one edge or one node from the previous answer. That is both inefficient and error-prone because different shortest paths can share edges or intermediate nodes.

The parent-list method is better because one BFS pass captures the full shortest-path structure cleanly.

No Path Case

If the target is never reached during BFS, then there is no path at all between the two nodes. In the code above, that case returns an empty list.

This matters in disconnected graphs, where undirected edges do not guarantee global connectivity.

Common Pitfalls

• Storing only one predecessor per node and losing alternative shortest paths.
• Using DFS alone and expecting it to discover shortest paths reliably.
• Re-running BFS repeatedly instead of capturing all shortest predecessors in one pass.
• Forgetting that the number of shortest paths can be large even in a modest graph.
• Backtracking without checking reachability first, which breaks when no path exists.

Summary

• In an unweighted undirected graph, BFS gives the shortest distance from the source.
• To find all shortest paths, store all valid predecessors, not just one.
• After BFS, backtrack from the target through the predecessor lists.
• The discovery phase is O(V + E), but output size may dominate if many shortest paths exist.
• This parent-list approach is the standard clean solution for enumerating every shortest path.