Shortest Path Visiting All Nodes

HardBitmask · BFS over (node, mask)🧩 Bitmask DP LeetCode #847 ↗Updated Oct 30, 2026

Problem

An undirected, connected graph with n nodes is given as an adjacency list (graph[i] = neighbours of i). Find the length (number of edges) of the shortest walk that visits every node. You may start and end anywhere, and revisit nodes and edges freely.

Input[[1,2,3],[0],[0],[0]]Output4 (1-0-2-0-3)

Input[[1],[0,2,4],[1,3,4],[2],[1,2]]Output4 (0-1-4-2-3)

1 ≤ n ≤ 12 · graph is undirected & connected · no self-loops or parallel edges

Try it yourself

Java

class Solution {
    public int shortestPathLength(int[][] graph) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The state is (node, visited set), not just the node. With n ≤ 12 the set is a bitmask → only n·2ⁿ ≈ 49k states, and a multi-source BFS over them finds the fewest steps to an all-ones mask.

PatternBitmask DP

Instinct n is tiny (about 20 or less) and you must use, visit or assign every item - make the set of used items a bitmask and DP over all 2^n subsets.

Memory hack Small n, big choice - let the bits keep score: each item is a light switch and the mask is the whole switch panel.

Open the Bitmask DP guide →

Approaches

Brute ForceAll Visit Orders + All-Pairs Distances

Time O(n · n!)Space O(n²)

A walk is fixed by the order of first visits; between consecutive ones, take the shortest path. So get all-pairs distances (Floyd–Warshall, O(n³)) and try every order.

Java

public int shortestPathLength(int[][] graph) {
    int n = graph.length, best = Integer.MAX_VALUE;
    int[][] d = allPairs(graph);
    for (int s = 0; s < n; s++) best = Math.min(best, orders(s, 1 << s, d));
    return best;
}
private int orders(int last, int mask, int[][] d) { // try every next node
    int n = d.length, best = mask == (1 << n) - 1 ? 0 : Integer.MAX_VALUE;
    for (int v = 0; v < n; v++)
        if ((mask >> v & 1) == 0)
            best = Math.min(best, d[last][v] + orders(v, mask | 1 << v, d));
    return best;
}
private int[][] allPairs(int[][] graph) { // Floyd-Warshall, unit edges
    int n = graph.length;
    int[][] d = new int[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(d[i], 1000);
        d[i][i] = 0;
        for (int j : graph[i]) d[i][j] = 1;
    }
    for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
        d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
    return d;
}

Correct but factorial: 12! ≈ 4.8·10⁸ orders.

BetterHeld–Karp Bitmask DP

Time O(2ⁿ · n²)Space O(2ⁿ · n)

Permutations repeat work: only the set already visited and the last node matter. dp[mask][u] = shortest walk that first-visits exactly mask and ends at u. Extend to an unvisited v with cost d[u][v]. Masks only grow, so increasing order is a valid topological order.

Java

public int shortestPathLength(int[][] graph) {
    int n = graph.length, full = (1 << n) - 1, INF = 1_000_000;
    int[][] d = allPairs(graph); // Floyd-Warshall (see Brute Force)
    int[][] dp = new int[1 << n][n];
    for (int[] row : dp) Arrays.fill(row, INF);
    for (int i = 0; i < n; i++) dp[1 << i][i] = 0;
    for (int mask = 1; mask <= full; mask++)
        for (int u = 0; u < n; u++)
            for (int v = 0; v < n; v++)
                if (dp[mask][u] < INF && (mask >> v & 1) == 0) {
                    int next = mask | 1 << v;
                    dp[next][v] = Math.min(dp[next][v], dp[mask][u] + d[u][v]);
                }
    return Arrays.stream(dp[full]).min().getAsInt();
}

Exponential, not factorial (~590k transitions at n = 12), but needs all-pairs first.

OptimalMulti-Source BFS on (node, mask)

Time O(2ⁿ · n²)Space O(2ⁿ · n)

Moves cost 1, so BFS over (node, mask) gives shortest distances. Seed all (i, 1<<i) (any start); a move to v gives (v, mask | 1<<v). The first popped state with a full mask is the answer. Work: O(2ⁿ·E).

Java

public int shortestPathLength(int[][] graph) {
    int n = graph.length, full = (1 << n) - 1;
    boolean[][] seen = new boolean[n][1 << n];
    Deque<int[]> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        queue.add(new int[]{i, 1 << i, 0}); // node, mask, steps
        seen[i][1 << i] = true;
    }
    while (true) { // connected graph: a full mask is always reached
        int[] cur = queue.poll();
        if (cur[1] == full) return cur[2];
        for (int v : graph[cur[0]]) {
            int mask = cur[1] | 1 << v;
            if (!seen[v][mask]) {
                seen[v][mask] = true;
                queue.add(new int[]{v, mask, cur[2] + 1});
            }
        }
    }
}

Same worst case, but no all-pairs step, faster on sparse graphs, stops early.

At a glance

Level	Approach	Time	Space
Brute Force	All Visit Orders + All-Pairs Distances	`O(n · n!)`	`O(n²)`
Better	Held–Karp Bitmask DP	`O(2ⁿ · n²)`	`O(2ⁿ · n)`
Optimal	Multi-Source BFS on (node, mask)	`O(2ⁿ · n²)`	`O(2ⁿ · n)`

Common pitfalls

Marking nodes, not (node, mask) states, as seen.
Seeding BFS from one node — the walk may start anywhere.
Treating it as a Hamiltonian path — reuse is allowed.

Interview tips

n ≤ 12 is a bitmask hint (2¹² = 4096).
State = (position, visited set) → plain unit-weight BFS.
Relate it to TSP / Held–Karp.

Pattern

BFS / DP over (node, bitmask) → shortest path that must collect or visit a small set (≤ ~15) of items.

My notes saved in this browser