Shortest Path Visiting All Nodes — Problem & Solution
Shortest Path Visiting All Nodes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Shortest Path Visiting All Nodes is a hard coding problem on breadth-first search, bit manipulation and graph, asked in Amazon, Google and Meta interviews.
- Difficulty: Hard
- Topics: Breadth-First Search, Bit Manipulation, Graph, Bitmask
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a connected undirected graph as adjacency lists: graph[i] lists the neighbours of node i.
Return the length of the shortest walk that visits every node. You may start and stop at any node, and you may revisit nodes and edges freely.
Example 1
Input: graph = [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: A star: one route is 1 → 0 → 2 → 0 → 3, four edges.
Example 2
Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: 0 → 1 → 4 → 2 → 3.
Example 3
Input: graph = [[1],[0]]
Output: 1
Constraints
2 <= graph.length <= 120 <= graph[i][j] < graph.lengthThe graph is connected and has no self-loops.
Hints for Shortest Path Visiting All Nodes
Hint 1
Revisiting is allowed, so the usual 'visited node' bookkeeping does not apply — what matters is which nodes have been covered so far.
Hint 2
A state is therefore a pair: the current node and a bitmask of covered nodes.
Hint 3
Breadth-first search over those
n · 2^nstates finds the shortest walk, seeded with every node as a possible start.
How to solve Shortest Path Visiting All Nodes
Expand the state from 'where am I' to 'where am I, and what have I covered'. Every edge traversal costs 1, so a breadth-first search over the expanded graph gives the shortest walk directly.
Approach
- Encode a state as
(node, mask), wheremaskhas bitvset when nodevhas been visited. - Seed the queue with
(i, 1 << i)for every nodei— the walk may start anywhere. - Expand a state by moving to each neighbour and setting its bit in the mask.
- The first state whose mask is all ones is at the answer's distance.
Why it works
The expanded graph has n · 2^n states and every edge has weight 1, so breadth-first search is exact. Seeding all starts at distance 0 is what lets the search find the best starting point without trying them one at a time. Revisits are harmless because a repeated (node, mask) is pruned and any genuinely new coverage produces a new state.
Complexity
- Time —
O(n² · 2^n) - Space —
O(n · 2^n)
Pitfalls
- Marking nodes rather than states visited prevents the legal revisits the problem depends on.
- Starting from a single node gives the shortest walk from that node, not the global shortest.
- Checking for completion when a state is dequeued — not when it is enqueued — keeps the distance bookkeeping simple.
Reference solution
Python
from collections import deque
from typing import List
def shortestPathLength(graph: List[List[int]]) -> int:
n = len(graph)
full = (1 << n) - 1
seen = set()
queue = deque()
for i in range(n):
queue.append((i, 1 << i, 0))
seen.add((i, 1 << i))
while queue:
node, mask, steps = queue.popleft()
if mask == full:
return steps
for nb in graph[node]:
nm = mask | (1 << nb)
if (nb, nm) not in seen:
seen.add((nb, nm))
queue.append((nb, nm, steps + 1))
return -1Java
public static int shortestPathLength(int[][] graph) {
int n = graph.length;
int full = (1 << n) - 1;
int size = full + 1;
boolean[] seen = new boolean[n * size];
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
int state = i * size + (1 << i);
seen[state] = true;
queue.add(state);
}
int steps = 0;
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int c = 0; c < levelSize; c++) {
int s = queue.poll();
int node = s / size;
int mask = s % size;
if (mask == full) return steps;
for (int nb : graph[node]) {
int ns = nb * size + (mask | (1 << nb));
if (!seen[ns]) { seen[ns] = true; queue.add(ns); }
}
}
steps++;
}
return -1;
}C++
int shortestPathLength(vector<vector<int>>& graph) {
int n = (int) graph.size();
int full = (1 << n) - 1;
int size = full + 1;
vector<bool> seen(n * size, false);
queue<int> q;
for (int i = 0; i < n; i++) {
int state = i * size + (1 << i);
seen[state] = true;
q.push(state);
}
int steps = 0;
while (!q.empty()) {
int levelSize = (int) q.size();
for (int c = 0; c < levelSize; c++) {
int s = q.front();
q.pop();
int node = s / size;
int mask = s % size;
if (mask == full) return steps;
for (int nb : graph[node]) {
int ns = nb * size + (mask | (1 << nb));
if (!seen[ns]) { seen[ns] = true; q.push(ns); }
}
}
steps++;
}
return -1;
}JavaScript
var shortestPathLength = function(graph) {
var n = graph.length;
var full = (1 << n) - 1;
var size = full + 1;
var seen = [];
for (var t = 0; t < n * size; t++) seen.push(false);
var queue = [];
for (var i = 0; i < n; i++) {
var state = i * size + (1 << i);
seen[state] = true;
queue.push(state);
}
var steps = 0;
while (queue.length > 0) {
var next = [];
for (var q = 0; q < queue.length; q++) {
var s = queue[q];
var node = Math.floor(s / size);
var mask = s % size;
if (mask === full) return steps;
for (var e = 0; e < graph[node].length; e++) {
var nb = graph[node][e];
var ns = nb * size + (mask | (1 << nb));
if (!seen[ns]) { seen[ns] = true; next.push(ns); }
}
}
queue = next;
steps++;
}
return -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 156 breadth-first search problems · the whole catalogue
Learn the technique: Breadth-First Search (BFS) · Bit Manipulation