Introduction

For an unweighted graph, the shortest path that visits all nodes is usually solved with breadth-first search over both position and visited-state. The key idea is that "where you are" is not enough; the algorithm also needs to know "which nodes have already been visited."

Why Ordinary BFS Is Not Enough

A normal BFS state is just the current node. That works for shortest path from one source to one destination, but it fails here because reaching the same node with different visited sets represents different progress.

For example, arriving at node 3 after visiting only 0 and 3 is not equivalent to arriving at node 3 after visiting 0, 1, 2, 3.

So the real state is:

• current node
• bitmask of visited nodes

The State-Space BFS Idea

If the graph has n nodes, let bit i in a mask indicate whether node i has been visited.

Examples for n = 4:

• mask 0001 means only node 0 visited
• mask 1011 means nodes 0, 1, and 3 visited
• mask 1111 means all nodes visited

The target mask is:

target = (1 << n) - 1

Once BFS reaches any state with that mask, the corresponding distance is the shortest number of edges needed to visit all nodes.

Start BFS from Every Node

This problem usually allows starting from any node. That means the best path might begin anywhere, so initialize the queue with all nodes as starting states.

That looks like this:

1from collections import deque
2
3def shortestPathLength(graph):
4    n = len(graph)
5    target = (1 << n) - 1
6    queue = deque()
7    seen = set()
8
9    for node in range(n):
10        mask = 1 << node
11        queue.append((node, mask, 0))
12        seen.add((node, mask))
13
14    while queue:
15        node, mask, dist = queue.popleft()
16
17        if mask == target:
18            return dist
19
20        for neighbor in graph[node]:
21            next_mask = mask | (1 << neighbor)
22            state = (neighbor, next_mask)
23            if state not in seen:
24                seen.add(state)
25                queue.append((neighbor, next_mask, dist + 1))

This is the standard and efficient solution for the common interview version of the problem.

Why This Produces the Shortest Path

BFS explores states in increasing order of distance. Since each edge traversal has equal cost, the first time you reach a state whose mask contains all nodes, you know no shorter path exists.

This works because:

• each transition adds exactly one edge to the path
• BFS processes distance d before distance d + 1
• the state includes enough information to distinguish useful revisits

Revisiting nodes is allowed, and that matters. Unlike a Hamiltonian path, the shortest route to cover all nodes may pass through some nodes more than once.

Example Walkthrough

Consider this graph:

1graph = [
2    [1, 2],
3    [0, 3],
4    [0, 3],
5    [1, 2]
6]
7
8print(shortestPathLength(graph))

One optimal route is 1 -> 0 -> 2 -> 3, which visits all four nodes in three edges. Starting BFS from every node allows the algorithm to discover that quickly.

Time and Space Complexity

There are at most n * 2^n distinct states:

• 'n choices for the current node'
• '2^n possible visited masks'

For each state, the algorithm iterates over the node's neighbors. So the typical complexity is:

• time: O(n * 2^n + m * 2^n) or commonly simplified to O(n * 2^n)
• space: O(n * 2^n)

That is feasible for small graphs, which is exactly why this pattern is popular in interview and contest problems.

Common Misunderstandings

This problem is often confused with the Traveling Salesman Problem. They are related, but not identical.

• TSP usually assumes weighted edges and often asks for a cycle returning to the start.
• "Shortest path to visit all nodes" in the common coding-problem form usually uses an unweighted graph and allows revisiting nodes.

That difference is why a BFS with bitmasks is appropriate here, whereas full TSP often requires dynamic programming over weighted distances or approximation methods.

Common Pitfalls

• Using a visited set keyed only by node causes incorrect pruning because different masks matter.
• Starting BFS from one node only can miss the optimal answer when the start is allowed to vary.
• Treating the problem like Hamiltonian path incorrectly forbids revisiting nodes.
• Forgetting the target mask (1 << n) - 1 leads to off-by-one bugs.
• Using DFS without memoization usually becomes much slower and more complicated.

Summary

• Model each BFS state as (current_node, visited_mask).
• Start from every node because the best path may begin anywhere.
• Use a bitmask to track which nodes have been visited.
• The first BFS state that reaches the all-visited mask gives the shortest answer.
• This is not the same as general weighted TSP, even though the problems are related.