DSA problem
Shortest Path Visiting All Nodes
You have an undirected, connected graph of n nodes labeled from 0 to n - 1. You are given an array graph where graph[i] is a list of all the nodes connected with node i by an edge. Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges. There are no self-loops or multi-edges.
Because the answer permits revisits, this is not a Hamiltonian path question — it is asking for the shortest walk that touches every node. We are free to choose any start, and intermediate nodes may repeat. The set of nodes already visited is what matters for future progress, not the exact path taken to reach them, so we need a state that captures (current node, visited set).
The natural encoding is a bitmask: visited is an n-bit integer whose i-th bit is set if node i has been touched. Together with the current node, the state space has size n * 2^n, which is tractable for n <= 12 (about 49152 states).
Because every edge has unit weight, BFS finds the shortest path. We initialize the BFS queue with every starting state (i, 1 << i) for i in 0..n - 1 (any node can be the start), each at distance 0. Each transition pops (u, mask) and pushes (v, mask | (1 << v)) for every neighbour v, incrementing the distance by 1. The first time we pop a state whose mask equals (1 << n) - 1 (every node visited), its distance is the answer. The visited[node][mask] table prevents revisiting states. Time and space are both O(n * 2^n).
Examples
graph = [[1,2,3],[0],[0],[0]]4graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]4graph = [[1],[0]]1Constraints
- n == graph.length
- 1 <= n <= 12
- 0 <= graph[i].length < n
- graph[i] does not contain i.
- The graph is connected and undirected; if graph[a] contains b, then graph[b] contains a.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.