Shortest Path Visiting All Nodes (LeetCode 847)

The problem

You get an undirected, connected graph with n ≤ 12 nodes as an adjacency list: graph[i] lists the neighbours of node i. Return the length (number of edges) of the shortest walk that visits every node. You may start and end anywhere, and you may revisit nodes and reuse edges.

Input:  graph = [[1, 2, 3], [0], [0], [0]]
        (a star: node 0 in the centre, 1, 2, 3 as leaves)
Output: 4

One shortest walk is 1 → 0 → 2 → 0 → 3: four edges, and every node is visited.

How to think about it

Start with brute force. Try every order of the nodes (n! permutations) and add up the shortest-path distances between consecutive nodes. For n = 12 that is 479 million orders, each with up to 11 legs. Too slow, and it needs all-pairs distances first.

Why plain BFS fails. BFS on nodes alone forbids revisiting a node, but here revisits are necessary (the star must pass through 0 three times). Standing at node 0 having seen {1} is a different situation from standing at node 0 having seen {1, 2}.

The key insight: make the state (node, visited set). Store the visited set as a bitmask. Now “revisit node 0” is fine, as long as the mask is different. Every edge costs 1, so BFS over these states finds the fewest edges to any state whose mask is full. There are only n · 2ⁿ states: 12 × 4096 ≈ 49,000.

Start everywhere at once. Since the walk can start at any node, seed the queue with (i, 1 << i) for every i. This multi-source BFS explores all starts in one pass.

Which pattern is this? Bitmask DP solved by BFS. The tell is n ≤ 12 and “visit all nodes”: a travelling-salesman flavour where the subset of visited nodes must be in the state.

Approach

1. Let full = (1 << n) - 1.
2. Put (i, 1 << i, 0) in the queue for each node, and mark (i, 1 << i) as seen.
3. Pop (node, mask, d). If mask == full, return d; BFS guarantees it’s the smallest.
4. For each neighbour nb, the new state is (nb, mask | (1 << nb)). If it’s unseen, mark it and push it with distance d + 1.
5. Return 0 if the loop ends (only for a one-node graph, which returns in step 3 anyway).

Solution

from collections import deque
def shortestPathLength(graph):
    n = len(graph); full = (1 << n) - 1
    q = deque((i, 1 << i, 0) for i in range(n))   # start from every node at once
    seen = {(i, 1 << i) for i in range(n)}
    while q:
        node, mask, d = q.popleft()
        if mask == full: return d                  # first full mask = fewest edges
        for nb in graph[node]:
            nm = mask | (1 << nb)
            if (nb, nm) not in seen:               # state = (where I am, what I've seen)
                seen.add((nb, nm)); q.append((nb, nm, d + 1))
    return 0
# shortestPathLength([[1,2,3],[0],[0],[0]]) -> 4

Dry run

Following the states (mask written as bits 3..0) along the walk the BFS finds, with parent pointers recorded while running the code:

The BFS popped 4, 6, 6 and 3 states at levels 0 to 3, then hit the full mask at level 4. Answer: 4.

Complexity

• Time: O(2ⁿ · n²). There are n · 2ⁿ states, and each is expanded once over up to n neighbours.
• Space: O(n · 2ⁿ). For the seen set and the queue.

Edge cases and pitfalls

• One node ([[]]): the start state already has the full mask, so the answer is 0.
• Keying seen on the node alone blocks the revisits the answer needs, and returns wrong or no results.
• Single-source BFS from node 0 is wrong; the best walk may start elsewhere. Seed every node, or loop over starts.
• DFS instead of BFS does not give shortest paths without extra DP; BFS works because all edges cost 1.
• The constraint matters. At n = 20, n² · 2ⁿ is around 400 million: mention that this only scales to small n.

Related problems

• Word Ladder (LeetCode 127): BFS on an implicit state graph for the fewest steps.
• Rotting Oranges (LeetCode 994): multi-source BFS seeded from many cells at once.
• Partition to K Equal Sum Subsets (LeetCode 698): bitmask state solved with memoised recursion.