Shortest Path Visiting All Nodes

Hard
748.

Shortest Path Visiting All Nodes

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.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} graph
 * @return {number}
 */
var shortestPathLength = function(graph) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.

Hints for Shortest Path Visiting All Nodes

  1. Hint 1

    Revisiting is allowed, so the usual 'visited node' bookkeeping does not apply — what matters is which nodes have been covered so far.

  2. Hint 2

    A state is therefore a pair: the current node and a bitmask of covered nodes.

  3. Hint 3

    Breadth-first search over those n · 2^n states 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

  1. Encode a state as (node, mask), where mask has bit v set when node v has been visited.
  2. Seed the queue with (i, 1 << i) for every node i — the walk may start anywhere.
  3. Expand a state by moving to each neighbour and setting its bit in the mask.
  4. 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

Java

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