Shortest Path Visiting All Nodes
Hard BFS over (node, visited-mask)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
In a connected undirected graph with n ≤ 12 nodes, return the length of the shortest walk that visits every node (you can start and end anywhere and reuse nodes and edges).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the shortest walk that visits every node.
Why this works: the state is (current node, set of visited nodes). BFS over those states finds the shortest walk.
Example: star graph 0 connected to 1, 2, 3
1 → 0 → 2 → 0 → 3 → 4 steps✦Hints open one at a time
↗Approach
Multi-source BFS with states (node, mask) and a seen[node][mask] table. The first time a state has all bits set, its distance is the answer.
</>Solution (Java)
import java.util.*;
class Solution {
public int shortestPathLength(int[][] graph) {
int n = graph.length, full = (1 << n) - 1;
boolean[][] seen = new boolean[n][1 << n];
Queue<int[]> q = new ArrayDeque<>(); // {node, mask}
for (int i = 0; i < n; i++) {
q.offer(new int[]{i, 1 << i});
seen[i][1 << i] = true;
}
for (int steps = 0; !q.isEmpty(); steps++) {
for (int s = q.size(); s > 0; s--) {
int[] cur = q.poll();
if (cur[1] == full) return steps;
for (int v : graph[cur[0]]) {
int mask = cur[1] | (1 << v);
if (!seen[v][mask]) {
seen[v][mask] = true;
q.offer(new int[]{v, mask});
}
}
}
}
return 0;
}
}!Common mistake
Marking only nodes as visited — you must be allowed to revisit a node with a different mask.
- Time: O(n² · 2^n).
- Space: O(n · 2^n).