Shortest Path Visiting All Nodes

hard graph dp bfs bitmask

Problem

Given an undirected, connected graph of n nodes, return the length of the shortest path that visits every node. You may revisit nodes and start from any node.

Inputgraph = [[1,2,3],[0],[0],[0]]

Output4

One shortest tour: 1 → 0 → 2 → 0 → 3 (4 edges).

adjacency (edges as "a-b" comma list)

from collections import deque
def shortestPathLength(graph):
    n = len(graph)
    full = (1 << n) - 1
    seen = set()
    q = deque()
    for i in range(n):
        q.append((i, 1 << i, 0))
        seen.add((i, 1 << i))
    while q:
        node, mask, d = q.popleft()
        if mask == full: return d
        for nb in graph[node]:
            nm = mask | (1 << nb)
            if (nb, nm) not in seen:
                seen.add((nb, nm))
                q.append((nb, nm, d + 1))
    return 0

function shortestPathLength(graph) {
  const n = graph.length, full = (1 << n) - 1;
  const seen = new Set(), q = [];
  for (let i = 0; i < n; i++) {
    q.push([i, 1 << i, 0]);
    seen.add(i + ',' + (1 << i));
  }
  let head = 0;
  while (head < q.length) {
    const [node, mask, d] = q[head++];
    if (mask === full) return d;
    for (const nb of graph[node]) {
      const nm = mask | (1 << nb);
      const key = nb + ',' + nm;
      if (!seen.has(key)) { seen.add(key); q.push([nb, nm, d + 1]); }
    }
  }
  return 0;
}

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

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

Explanation

We need the shortest walk that touches every node, and we may revisit nodes and start anywhere. The key insight is that a state isn't just "where am I" but "where am I and which nodes have I already visited." We capture the visited set as a bitmask and run BFS over (node, mask) states.

Because we can begin from any node, we seed the queue with all of them: each start i enters as (i, 1 << i, 0) — at node i, having visited only i, distance 0. The target mask full = (1 << n) - 1 has every bit set, meaning all nodes seen.

From a state we walk to each neighbor nb, forming a new mask nm = mask | (1 << nb). We only enqueue a (nb, nm) state we haven't seen before. The first popped state whose mask == full gives the shortest answer, since BFS explores by increasing distance.

Example: graph = [[1,2,3],[0],[0],[0]] is a star centered at 0. One shortest tour is 1 → 0 → 2 → 0 → 3, using 4 edges, and that's what the BFS returns.

Tracking the visited mask is what lets us safely revisit node 0 multiple times without looping forever — each revisit carries a different, growing set of visited nodes.

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