Problem 32.9 · Advanced DPHard

Shortest Path Visiting All Nodes

What it teaches: BFS over (node, visited-mask) states: a bitmask in a graph search.

Practise it on judges as “Shortest Path Visiting All Nodes”.

The problem

In a connected undirected graph with n ≤ 12 nodes, return the length of the shortest walk that visits every node. You may start and end anywhere and reuse nodes and edges.

Example 1

Input: graph = [[1,2,3],[0],[0],[0]]
Output: 4

Constraints

1 ≤ n ≤ 12

Pattern clues in the wording

→ Visit all nodes
→ Tiny n

These clues point to Bitmask DP: Represent which items are used as the bits of an integer, so dp[mask] covers every subset (n up to about 20).

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

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

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	graph = [[1,2,3],[0],[0],[0]]	4
2	graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]	4

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. BFS over (node, mask) · O(2ⁿ × n²)

BFS over (node, mask)

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

Start with all (i, 1 << i) at distance 0. BFS; moving to v sets mask | (1 << v). The first state with a full mask gives the answer.

Approach 1

import java.util.*;

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}); seen[i][1 << i] = true; }
        for (int steps = 0; !q.isEmpty(); steps++) {
            for (int size = q.size(); size > 0; size--) {
                int[] s = q.poll();
                if (s[1] == full) return steps;
                for (int v : graph[s[0]]) {
                    int mask = s[1] | (1 << v);
                    if (!seen[v][mask]) { seen[v][mask] = true; q.offer(new int[]{v, mask}); }
                }
            }
        }
        return 0;
    }
}

Verdict: Unweighted, so BFS gives the shortest walk.

Before you submit

Edge cases and common mistakes

Test these inputs

Single node (0)
A star graph (revisiting the centre)

Mistakes people make

Tracking visited nodes only (walks must be allowed to revisit).

Interview

Follow-up questions

How does this relate to the travelling salesman problem?

Command Palette

The problem

Approaches

BFS over (node, mask)

Edge cases and common mistakes

Follow-up questions