LeetCode · #847

Shortest Path Visiting All Nodes Solution

Find the minimum number of edges needed to visit every node in an undirected graph. You may start at any node, revisit nodes, and reuse edges.

Section One · Problem

Problem Statement

🏷️

Difficulty

Hard

🔗

LeetCode

Problem #847

🏗️

Pattern

BFS on state space with bitmask

Because revisits are allowed, the real state is not just “which node am I on?” It is:

(currentNode, visitedMask)

where visitedMask marks which nodes have been seen so far. The target is any state whose mask has all bits set.

Example

Input:  graph = [[1,2,3],[0],[0],[0]]
Output: 4
// One shortest route is 1 → 0 → 2 → 0 → 3

Section Two · Approach 1

Backtracking Over State Space — Exponential

A brute-force strategy is to recursively try every walk, remember the set of visited nodes, and keep the minimum length once all nodes have been seen.

Why it works

If we enumerate every possible walk, then eventually we discover the shortest walk that covers all nodes.

Problem: Different walks often land in the same state (node, mask). From that point onward, the future possibilities are identical. BFS over these deduplicated states is dramatically better and automatically gives the shortest number of edges because the graph is unweighted.

Section Three · Approach 2

Multi-source BFS on (node, mask) States — O(V · 2^V)

Start BFS simultaneously from every node, because the problem lets us choose any start. The initial states are (i, 1 << i) for all nodes i. From a state (u, mask), moving to neighbor v gives the next state (v, mask | (1 << v)).

💡 Mental model: Imagine every node launching its own explorer at time 0. Each explorer carries a checklist of visited nodes. BFS spreads all explorers outward one step at a time. The first explorer whose checklist is fully checked has found the globally shortest route.

Let finalMask = (1 << n) - 1.
Initialize the queue with all n starting states.
Use visited[node][mask] to avoid reprocessing the same state.
For each BFS move, update the mask with the destination node bit.
The first state reaching finalMask gives the shortest path length.

Recognition signal:

When the prompt asks to “visit all nodes / collect all keys / cover all subsets” with an unweighted graph, think BFS on position + bitmask.
The node alone is not enough state.

Section Four · Trace

Visual Walkthrough

Trace graph = [[1,2,3],[0],[0],[0]].

Shortest Path Visiting All Nodes — BFS state expansion

Section Five · Implementation

Code — Java & Python

Java — multi-source BFS with bitmask

import java.util.*;

class Solution {
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        if (n == 1) return 0;

        int finalMask = (1 << n) - 1;
        Queue<int[]> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[n][1 << n];

        for (int node = 0; node < n; node++) {
            int mask = 1 << node;
            queue.offer(new int[] { node, mask });
            visited[node][mask] = true;
        }

        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] state = queue.poll();
                int node = state[0], mask = state[1];
                if (mask == finalMask) return steps;

                for (int nei : graph[node]) {
                    int nextMask = mask | (1 << nei);
                    if (visited[nei][nextMask]) continue;
                    visited[nei][nextMask] = true;
                    queue.offer(new int[] { nei, nextMask });
                }
            }
            steps++;
        }

        return -1;
    }
}

Python — BFS on compressed state graph

from collections import deque

class Solution:
    def shortestPathLength(self, graph: list[list[int]]) -> int:
        n = len(graph)
        if n == 1:
            return 0

        final_mask = (1 << n) - 1
        queue = deque()
        visited = [[False] * (1 << n) for _ in range(n)]

        for node in range(n):
            mask = 1 << node
            queue.append((node, mask))
            visited[node][mask] = True

        steps = 0
        while queue:
            for _ in range(len(queue)):
                node, mask = queue.popleft()
                if mask == final_mask:
                    return steps

                for nei in graph[node]:
                    next_mask = mask | (1 << nei)
                    if visited[nei][next_mask]:
                        continue
                    visited[nei][next_mask] = True
                    queue.append((nei, next_mask))
            steps += 1

        return -1

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Backtracking state search	Explosive / exponential	O(V) recursion + visited set	Repeatedly solves the same subproblems.
BFS on (node, mask) ← optimal	O(V · 2^V + E · 2^V)	O(V · 2^V)	Every unique state is processed at most once.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Expected behavior	Why it matters
Single-node graph	Return `0`	All nodes are already visited.
Any start allowed	Use multi-source BFS	Starting from only one node can miss the optimal route.
Revisiting nodes	Allowed and often necessary	Do not use a simple visited-node set.
State deduplication	Use `visited[node][mask]`	Same node with different masks are different states.
Stopping condition	Check `mask == finalMask`	Visiting all nodes matters, not arriving at one special destination.

⚠ Common Mistake: Marking just visited[node]. That loses essential information. Reaching node 3 after visiting 3 is completely different from reaching node 3 after visiting 3. The mask must be part of the state.

← Back to Shortest Path

LearningTree

LC 847 · Shortest Path Visiting All Nodes — Solution & Explanation | DSA Guide