Shortest Path Visiting All Nodes

Problem#

Given an undirected, connected graph on n nodes, return the shortest path that visits every node at least once. You can revisit nodes and edges and start anywhere.

Examples#

graph = [[1,2,3],[0],[0],[0]] → 4
graph = [[1],[0,2,4],[1,3,4],[2],[1,2]] → 4

Constraints#

n == graph.length, 1 <= n <= 12.

Approach#

State = (currentNode, visitedBitmask). Multi-source BFS starting from every node with its own bit set. Pop a state, try every neighbor, set its bit, enqueue if unseen. Return the layer at which any state with bitmask (1<<n) - 1 is first popped.

Solution#

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        int full = (1 << n) - 1;
        vector<vector<bool>> seen(n, vector<bool>(full + 1, false));
        queue<tuple<int,int,int>> q;
        for (int i = 0; i < n; ++i) {
            int mask = 1 << i;
            q.push({i, mask, 0});
            seen[i][mask] = true;
        }
        while (!q.empty()) {
            auto [u, mask, d] = q.front(); q.pop();
            if (mask == full) return d;
            for (int v : graph[u]) {
                int nm = mask | (1 << v);
                if (!seen[v][nm]) {
                    seen[v][nm] = true;
                    q.push({v, nm, d + 1});
                }
            }
        }
        return 0;
    }
};

func shortestPathLength(graph [][]int) int {
    n := len(graph)
    full := (1 << n) - 1
    seen := make([][]bool, n)
    for i := range seen {
        seen[i] = make([]bool, full+1)
    }
    type state struct{ u, mask, d int }
    q := []state{}
    for i := 0; i < n; i++ {
        mask := 1 << i
        q = append(q, state{i, mask, 0})
        seen[i][mask] = true
    }
    for len(q) > 0 {
        s := q[0]
        q = q[1:]
        if s.mask == full {
            return s.d
        }
        for _, v := range graph[s.u] {
            nm := s.mask | (1 << v)
            if !seen[v][nm] {
                seen[v][nm] = true
                q = append(q, state{v, nm, s.d + 1})
            }
        }
    }
    return 0
}

from collections import deque
from typing import List

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        n = len(graph)
        full = (1 << n) - 1
        seen = [[False] * (full + 1) for _ in range(n)]
        q = deque()
        for i in range(n):
            mask = 1 << i
            q.append((i, mask, 0))
            seen[i][mask] = True
        while q:
            u, mask, d = q.popleft()
            if mask == full:
                return d
            for v in graph[u]:
                nm = mask | (1 << v)
                if not seen[v][nm]:
                    seen[v][nm] = True
                    q.append((v, nm, d + 1))
        return 0

function shortestPathLength(graph) {
    const n = graph.length;
    const full = (1 << n) - 1;
    const seen = Array.from({ length: n }, () => new Uint8Array(full + 1));
    const q = [];
    for (let i = 0; i < n; i++) {
        const mask = 1 << i;
        q.push([i, mask, 0]);
        seen[i][mask] = 1;
    }
    let head = 0;
    while (head < q.length) {
        const [u, mask, d] = q[head++];
        if (mask === full) return d;
        for (const v of graph[u]) {
            const nm = mask | (1 << v);
            if (!seen[v][nm]) {
                seen[v][nm] = 1;
                q.push([v, nm, d + 1]);
            }
        }
    }
    return 0;
}

class Solution {
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        int full = (1 << n) - 1;
        boolean[][] seen = new boolean[n][full + 1];
        Deque<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            int mask = 1 << i;
            q.offer(new int[]{i, mask, 0});
            seen[i][mask] = true;
        }
        while (!q.isEmpty()) {
            int[] s = q.poll();
            int u = s[0], mask = s[1], d = s[2];
            if (mask == full) return d;
            for (int v : graph[u]) {
                int nm = mask | (1 << v);
                if (!seen[v][nm]) {
                    seen[v][nm] = true;
                    q.offer(new int[]{v, nm, d + 1});
                }
            }
        }
        return 0;
    }
}

function shortestPathLength(graph: number[][]): number {
    const n = graph.length;
    const full = (1 << n) - 1;
    const seen: Uint8Array[] = Array.from({ length: n }, () => new Uint8Array(full + 1));
    const q: [number, number, number][] = [];
    for (let i = 0; i < n; i++) {
        const mask = 1 << i;
        q.push([i, mask, 0]);
        seen[i][mask] = 1;
    }
    let head = 0;
    while (head < q.length) {
        const [u, mask, d] = q[head++];
        if (mask === full) return d;
        for (const v of graph[u]) {
            const nm = mask | (1 << v);
            if (!seen[v][nm]) {
                seen[v][nm] = 1;
                q.push([v, nm, d + 1]);
            }
        }
    }
    return 0;
}

Editorial#

The state space is n * 2^n, which fits easily at n = 12. Multi-source BFS handles “start anywhere” by initializing every node as a layer-0 state. Layer numbers correspond directly to path length.

Complexity#

Time: O(2^n * n^2) in the worst case (each state explores its neighbors).
Space: O(2^n * n).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#