Lab 10 — Bitmask DP (Shortest Path Visiting All Nodes)

Goal

Solve Shortest Path Visiting All Nodes (LC 847) with both BFS over (node, mask) states and an iterative DP variant. Internalize bitmask state encoding: when N is small (≤ 20), the subset S ⊆ {0, …, N-1} fits in a single integer mask and a 1D array of size 2^N indexes all subsets. After this lab you can handle any “visit all / cover all / select subset” problem with N ≤ 20 in <15 minutes.

Background Concepts

Bitmask DP encodes a subset as an integer’s bits. For N=12, there are 2^12 = 4096 subsets — small enough that dp[mask][i] (mask × last-visited-node) has 4096 × 12 ≈ 50K states. Each state’s transition is O(N), giving O(N² · 2^N) total — feasible for N ≤ 16, manageable for N ≤ 20 with care.

Common bitmask DP patterns:

  1. Visit-all / TSP-like: dp[mask][i] = min cost to visit nodes in mask ending at i. Final: min over i of dp[(1<<N)-1][i] (+ return-to-start cost for TSP).
  2. Subset-cover: dp[mask] = best score selecting items whose indicator is mask.
  3. Assignment problems: assign N people to N tasks with min total cost — dp[mask] where mask = set of tasks already assigned, with popcount(mask) people processed so far.

LC 847 is unusual: it’s a shortest unweighted path problem (BFS), not a min-cost (Dijkstra) problem. So BFS over (node, mask) is the natural approach. We can also frame it as DP, but BFS is cleaner here.

Interview Context

Shortest Path Visiting All Nodes (LC 847) is a top-Hard graph + bitmask problem at Google and Meta. The bitmask-on-graph technique recurs in: LC 943 (Find the Shortest Superstring), LC 1125 (Smallest Sufficient Team), LC 1349 (Maximum Students Taking Exam), LC 526 (Beautiful Arrangement). The trick of recognizing N ≤ 20 → bitmask is itself an interview heuristic: any time N is suspiciously small, consider bitmask.

Problem Statement

You have an undirected, connected graph of n nodes labeled from 0 to n − 1. graph[i] is the list of neighbors of node i. Return the length of the shortest path that visits every node. You may start and stop at any node, may revisit nodes, and may reuse edges.

Constraints

  • 1 ≤ n ≤ 12
  • graph.length == n
  • 0 ≤ graph[i].length < n
  • The graph is connected.

Clarifying Questions

  1. Edges are undirected? (Yes — given.)
  2. Edges weighted or unweighted? (Unweighted — count edges traversed.)
  3. Can the same node be visited multiple times? (Yes.)
  4. Can we start anywhere? (Yes — the answer minimizes over all starting nodes.)
  5. Must the graph be connected? (Yes — given. Otherwise the answer is infeasible.)

Examples

graph = [[1,2,3],[0],[0],[0]]      → 4   (visit order: 1→0→2→0→3 or 2→0→1→0→3 etc.)
graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]   → 4

graph = [[1],[0]]                  → 1   (just edge 0–1)
graph = [[]]                       → 0   (single node, already visited)

Initial Brute Force

Try every permutation of node visits as a starting path; sum the shortest-path-lengths between consecutive nodes (precomputed via BFS). N! permutations × O(N) work per permutation. At N=12, 12! ≈ 5 × 10^8 — borderline.

from itertools import permutations
from collections import deque

def shortestPathLength_brute(graph):
    n = len(graph)
    if n == 1: return 0
    # Precompute pairwise shortest path lengths via BFS
    dist = [[float('inf')] * n for _ in range(n)]
    for src in range(n):
        dist[src][src] = 0
        q = deque([src])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if dist[src][v] == float('inf'):
                    dist[src][v] = dist[src][u] + 1
                    q.append(v)
    best = float('inf')
    for perm in permutations(range(n)):
        cost = sum(dist[perm[i]][perm[i+1]] for i in range(n - 1))
        best = min(best, cost)
    return best

Brute Force Complexity

O(N! · N) time. At N=12, infeasible.

Optimization Path

Observation: at any point, the relevant state is (current_node, set_of_visited_nodes). There are N · 2^N such states. Two ways to solve:

  1. BFS over states (canonical for unweighted): each state is a node in a meta-graph of (node, mask); transitions to (neighbor, mask | (1 << neighbor)). BFS gives shortest-path lengths to all states; the answer is the smallest distance to any state with mask = (1 << N) - 1. Time O(N · 2^N · degree) ≈ O(N² · 2^N).

  2. Iterative DP (Held-Karp style for TSP — but TSP minimizes weighted paths; for unweighted with revisits the BFS is more natural).

We present BFS as the primary solution (canonical for LC 847) with the iterative-DP variant as a follow-up.

Final Expected Approach

1. Initialize a queue with all (node, 1 << node) states (one per starting node), distance 0.
2. BFS:
   - Pop (u, mask). If mask == ALL = (1<<N)-1, return current distance.
   - For each neighbor v of u:
       new_mask = mask | (1 << v)
       if (v, new_mask) not yet visited:
           mark, enqueue, distance + 1.

Data Structures Used

  • deque for BFS.
  • 2D visited[node][mask] boolean (or a set of (node, mask) tuples).
  • For brute force: pairwise dist table (BFS-precomputed) and itertools.permutations.

Correctness Argument

The state graph has nodes (u, mask) and edges (u, mask) → (v, mask | (1 << v)) for every graph neighbor v of u. A path in the original graph that visits all nodes corresponds 1-to-1 to a path in the state graph from some starting state (s, 1 << s) to a “complete” state (t, ALL) for some t. Since the state-graph edges are unweighted, BFS finds the shortest such path. Multi-source BFS over all starting states minimizes over all start nodes simultaneously. Termination: the state graph has N · 2^N nodes; BFS visits each at most once.

Complexity

StageTimeSpace
Brute force (perm + BFS dist)O(N! · N + N²·E)O(N²)
BFS over (node, mask)O(N² · 2^N)O(N · 2^N)
DP (popcount-ascending fill)O(N² · 2^N)O(N · 2^N)

At N=12: 12² · 4096 = 590K ops — fast.

Implementation Requirements

from collections import deque
from itertools import permutations

# ---- Stage 1: Brute force ----
def shortestPathLength_brute(graph):
    n = len(graph)
    if n == 1: return 0
    dist = [[float('inf')] * n for _ in range(n)]
    for src in range(n):
        dist[src][src] = 0
        q = deque([src])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if dist[src][v] == float('inf'):
                    dist[src][v] = dist[src][u] + 1
                    q.append(v)
    best = float('inf')
    for perm in permutations(range(n)):
        cost = sum(dist[perm[i]][perm[i+1]] for i in range(n - 1))
        if cost < best: best = cost
    return best

# ---- Stage 2: Memoized DFS over (node, mask) — works but BFS is preferred for unweighted ----
from functools import lru_cache
def shortestPathLength_memo(graph):
    n = len(graph)
    ALL = (1 << n) - 1
    @lru_cache(None)
    def f(u, mask):
        if mask == ALL: return 0
        best = float('inf')
        for v in graph[u]:
            new_mask = mask | (1 << v)
            if new_mask != mask:  # only progress if v is newly visited
                best = min(best, 1 + f(v, new_mask))
            # also allow revisiting (no-op for mask but adds 1 to path length) -- but that's wasteful, skip
        return best
    # Try every starting node
    return min(f(s, 1 << s) for s in range(n))
# NOTE: this memo version misses cases where you must transit through already-visited nodes.
# BFS handles that natively because (v, new_mask) where new_mask == mask is allowed if not yet seen.

# ---- Stage 3: BFS over (node, mask) — canonical solution ----
def shortestPathLength(graph):
    n = len(graph)
    if n == 1: return 0
    ALL = (1 << n) - 1
    visited = set()
    q = deque()
    for s in range(n):
        state = (s, 1 << s)
        visited.add(state)
        q.append((s, 1 << s, 0))
    while q:
        u, mask, dist = q.popleft()
        if mask == ALL: return dist
        for v in graph[u]:
            new_mask = mask | (1 << v)
            state = (v, new_mask)
            if state not in visited:
                visited.add(state)
                q.append((v, new_mask, dist + 1))
    return -1  # unreachable; should not happen for connected graphs

# ---- Stage 4: DP filling by mask in popcount order (alternative formulation) ----
def shortestPathLength_dp(graph):
    n = len(graph)
    if n == 1: return 0
    ALL = (1 << n) - 1
    INF = float('inf')
    # dp[mask][u] = min edges to reach state (u, mask) from any starting node
    dp = [[INF] * n for _ in range(1 << n)]
    q = deque()
    for s in range(n):
        dp[1 << s][s] = 0
        q.append((s, 1 << s))
    while q:
        u, mask = q.popleft()
        for v in graph[u]:
            new_mask = mask | (1 << v)
            if dp[new_mask][v] > dp[mask][u] + 1:
                dp[new_mask][v] = dp[mask][u] + 1
                q.append((v, new_mask))
    return min(dp[ALL][u] for u in range(n))

Tests

  • [[1,2,3],[0],[0],[0]] → 4.
  • [[1],[0,2,4],[1,3,4],[2],[1,2]] → 4.
  • [[1],[0]] → 1.
  • [[]] → 0 (single node).
  • N=12 with sparse and dense connectivity — performance smoke.
  • Cross-check brute vs BFS on N≤6 random connected graphs.

Follow-up Questions

  1. “What if edges are weighted?” → Replace BFS with Dijkstra (priority queue). Still O((N · 2^N) log(N · 2^N) + edges).
  2. “Must return to start (TSP closed tour).” (Held-Karp) → Compute dp[mask][u] = min cost from start to u visiting mask; final answer min over u of dp[ALL][u] + dist[u][start].
  3. “Can revisit, weighted, must visit all.” → Floyd-Warshall preprocess to get all-pairs shortest paths, then Held-Karp on the dense complete graph induced by those distances.
  4. “N up to 20 — does this still fit?” → 2^20 = 10^6, N²·2^N ≈ 4×10^8. Borderline; need bit tricks and tight inner loops, often C++/Java only.
  5. “All Hamiltonian paths (visit each node exactly once).” → Same DP; track exact popcount(mask) == N. NP-hard but bitmask handles N≤20.

Product Extension

The bitmask DP / Held-Karp algorithm is the gold-standard exact solution for small TSP-like problems. Real applications: drone delivery routing for ≤ 20 stops, layout optimization in chip design, scheduling N jobs on a single machine with sequence-dependent setup times, optimal-question-ordering in adaptive testing.

Language/Runtime Follow-ups

  • Python: bit operations (|, &, <<) on ints are arbitrary-precision; (1 << N) - 1 works for any N. Use bin(mask).count('1') for popcount, or mask.bit_count() in Python 3.10+.
  • Java: Integer.bitCount(mask). Use int for N ≤ 31, long for N ≤ 63.
  • Go: bits.OnesCount(uint(mask)) from math/bits.
  • C++: __builtin_popcount(mask) (or popcount in C++20). Compiles to a single CPU instruction.
  • JS/TS: bitwise ops are 32-bit signed; for N > 30 use BigInt (slower).

Common Bugs

  1. Forgetting to multi-source initialize the BFS — a single starting node misses better starts.
  2. Treating (v, new_mask) where new_mask == mask as visited and skipping — this is correct for BFS if the state was already enqueued, but new code may forget that revisiting is sometimes necessary (transit through known nodes). The state-key (v, mask) handles this automatically.
  3. mask | (1 << v) missing the parentheses: mask | 1 << v parses as (mask | 1) << v in C/Java/JS — wrong. Always parenthesize the shift.
  4. Forgetting the if mask == ALL: return dist check at dequeue time — checking only at enqueue can miss a dist+1 opportunity.
  5. set of tuples performance: in Python, a 2D bool array is faster than a set for the visited check at high N. Use [[False]*N for _ in range(1<<N)].

Debugging Strategy

For [[1,2,3],[0],[0],[0]] (N=4): BFS expands (0,0001), (1,0010), (2,0100), (3,1000) at distance 0. From (1,0010), we go to (0,0011) at distance 1. From (0,0011), we go to (1,0011), (2,0111), (3,1011) at distance 2. From (2,0111) we go to (0,0111) at distance 3. From (0,0111) we go to (3,1111) at distance 4 — done. Print (u, bin(mask), dist) per dequeue and locate where your trace diverges.

Mastery Criteria

  • Recognized “N ≤ 12, visit all” as bitmask DP within 60 seconds.
  • Stated the state space (node, mask) and its size N · 2^N in <30 seconds.
  • Wrote the multi-source BFS in <8 minutes from blank screen.
  • Articulated why multi-source initialization is correct (start anywhere).
  • Stated O(N² · 2^N) time complexity.
  • Solved LC 847 unaided in <20 minutes.
  • Articulated the difference between BFS-over-states (unweighted) and Held-Karp (weighted/TSP) in <60 seconds.
  • Wrote mask.bit_count() / __builtin_popcount correctly without prompting.
  • Solved LC 526 (Beautiful Arrangement) in <12 minutes using dp[mask] over assignments.