DP — Shortest Path Visiting All Nodes
↗ LeetCode: Shortest Path Visiting All Nodes · Hard · pattern chapter →
Undirected graph. Shortest length path visiting every node (may reuse).
Example 1 — graph=[[1,2,3],[0],[0],[0]] → 4 (star: hop out and back) Example 2 — graph=[[1],[0,2,4],[1,3,4],[2],[1,2]] → 4Example 3 — graph=[[1],[0]] → 1
Constraints — 1 ≤ n ≤ 12. Brute permutation of routes is O(n!·n) = 12!·12 ≈ 6·10⁹ ops = TLE. Bitmask BFS is O(n·2ⁿ·deg) ≤ 12·4096·12 = 6·10⁵ ops = <10ms.
Interview timer00:00
Approach 1 — Brute permutation
Intuition. Try every permutation of visit order; compute path length (BFS between consecutive pair). Return min.
Complexity — Time O(n!·n²); Space O(n). TLE past n=9. In an interview say "state (node, visitedMask) collapses redundant orderings — bitmask BFS → O(n·2ⁿ)."
Approach 2 — Bitmask BFS (canonical)
Insight. State = (node, visitedMask). BFS from all (i, 1 << i) starts simultaneously; first to hit mask == full wins.
int shortestPathLength(int[][] graph) {
int n = graph.length, full = (1 << n) - 1;
Queue<int[]> q = new ArrayDeque<>();
boolean[][] seen = new boolean[n][1 << n];
for (int i = 0; i < n; i++) {
q.offer(new int[]{i, 1 << i});
seen[i][1 << i] = true;
}
int steps = 0;
while (!q.isEmpty()) {
for (int sz = q.size(); sz > 0; sz--) {
int[] c = q.poll();
if (c[1] == full) return steps;
for (int nb : graph[c[0]]) {
int nMask = c[1] | (1 << nb);
if (!seen[nb][nMask]) { seen[nb][nMask] = true; q.offer(new int[]{nb, nMask}); }
}
}
steps++;
}
return -1;
}Complexity — Time O(n · 2ⁿ · degree); Space O(n · 2ⁿ). Say aloud in an interview: "bitmask-on-visited pattern — same as Traveling Salesman, Number of Ways to Wear Different Hats."
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Brute permutation | O(n!·n²) | O(n) | TLE past n=9 |
| Bitmask BFS | O(n · 2ⁿ · deg) | O(n · 2ⁿ) | Canonical |
When to use which
- Small n + reachable revisits → bitmask BFS.
- Exact TSP → same DP.
- k people delivery → k-source BFS extension.