Shortest Path Visiting All Nodes — Hard Problem & Solution

You are given a connected undirected graph as adjacency lists: graph[i] lists the neighbours of node i.

Difficulty: Hard
Topics: Bit Manipulation, Breadth-First Search, 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 <= 12
0 <= graph[i][j] < graph.length
The graph is connected and has no self-loops.

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), where mask has bit v set when node v has been visited.
Seed the queue with (i, 1 << i) for every node i — 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 -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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 83 bit manipulation problems · the whole catalogue