Shortest Path Visiting All Nodes

Problem in Plain English

Find the fewest edge traversals needed to visit every vertex of a connected undirected graph. Choose any starting and ending vertices; vertices and edges may be used repeatedly.

Problem Statement

Given an adjacency list graph for a connected undirected graph whose vertices are numbered from 0 to n - 1, return the length of a shortest walk visiting every vertex. Length counts traversed edges, not distinct vertices. You may start and finish anywhere, revisit a vertex, and traverse an edge more than once.

The official problem calls this a path, but repeated vertices are explicitly allowed. A Hamiltonian path, which visits each vertex exactly once, is not required.

Constraints

n == graph.length and 1 <= n <= 12.
0 <= graph[i].length < n; a vertex is not its own neighbor.
Adjacency is symmetric: if b is in graph[a], then a is in graph[b].
The graph is connected.

Examples

Example 1

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

Walk 1 → 0 → 2 → 0 → 3 visits every vertex in four edges. Three leaves require two passages through the center between leaf visits, so three edges cannot suffice.

Example 2

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

Walk 0 → 1 → 4 → 2 → 3 uses four edges. Visiting five distinct vertices requires at least four edges, so this walk attains the lower bound.

Example 3

Input: graph = [[]]
Output: 0

The starting vertex already covers the whole graph. No edge needs to be traversed.

Intuition

Remember both where the walk ends and which vertices it has already visited. A bitmask stores that visited set: bit v is one exactly when vertex v has been seen. In Example 1, the star cannot be covered without returning through its center: 1 → 0 → 2 → 0 → 3 takes four edges. Reaching vertex 0 with mask 0011 is a different state from reaching it with mask 0111; the second walk has already covered another leaf. The mask never loses bits, but a move can leave it unchanged, so a simple increasing-mask DP loop cannot settle every distance. Breadth-first search settles the minimum distance to each state instead.

Approaches

Bitmask BFS

Optimal

Solution Details

Reveal Bitmask BFS: intuition, complexity, and code

Intuition

Search the graph of endpoint-and-visited-set states in breadth-first order from every possible starting vertex. Enumerating walks directly repeats prefixes indefinitely because vertices may be revisited; merging equivalent states removes that bottleneck. Initialize (v, 1 << v) at distance zero for every v, then traverse an original edge to u with new mask mask | (1 << u). Mark states when enqueuing them. The first dequeued full mask has minimum length across all starts. This uses the unweighted shortest-path invariant described in MIT’s BFS notes.

Step-by-Step Logic

For Example 1, set full = 1111 and enqueue (0,0001), (1,0010), (2,0100), (3,1000) at distance zero.
From start 1, reach center state (0,0011) after one edge.
Move to leaf 2: state (2,0111) now has distance two.
Return to center: (0,0111) has distance three. It is new even though vertex 0 was seen before.
Move to leaf 3: (3,1111) has distance four. When a full-mask state is removed from the queue, return 4.

Why It Works

Each original walk corresponds to a state walk with the same edge count: the endpoint changes along the original edge and the mask records the union of all visited vertices. Conversely, every state transition is an actual original edge, so a full mask describes a valid covering walk. Two prefixes at the same (node, mask) have exactly the same available future transitions. Keeping only their earliest arrival cannot remove a shorter solution. Multi-source initialization is equivalent to giving every allowed start distance zero. FIFO BFS processes distances in nondecreasing order, so its first full-mask removal is globally shortest. Revisiting a vertex is allowed; only a repeated entire state is discarded. Connectivity guarantees a covering walk exists.

Dry Run

Bitmask BFS: variable states at each step
Distance	Representative state removed	Transition on a shortest witness
0	`(1,0010)`	Enqueue `(0,0011)`
1	`(0,0011)`	Enqueue `(2,0111)`
2	`(2,0111)`	Enqueue `(0,0111)`
3	`(0,0111)`	Enqueue `(3,1111)`
4	`(3,1111)`	Full mask; return 4

Complexity Analysis

Time Complexity

O((n+m)2^n)

Space Complexity

O(n2^n)

Here m is the number of undirected edges. At most n times 2^n endpoint-mask states enter the queue; summed neighbor scans are at most 2m times 2^n. The seen table and queue hold O(n times 2^n) entries, at most 49,152 for n = 12. There is no recursion.

Code

Solution.java

1import java.util.ArrayDeque;2
3class Solution {4    public int shortestPathLength(int[][] graph) {5        int n = graph.length, full = (1 << n) - 1;6        boolean[][] seen = new boolean[n][1 << n];7        ArrayDeque<int[]> queue = new ArrayDeque<>();8        for (int v = 0; v < n; v++) {9            seen[v][1 << v] = true;10            queue.add(new int[]{v, 1 << v, 0});11        }12        while (!queue.isEmpty()) {13            int[] state = queue.remove();14            int v = state[0], mask = state[1], distance = state[2];15            if (mask == full) return distance;16            for (int u : graph[v]) {17                int next = mask | (1 << u);18                if (!seen[u][next]) {19                    seen[u][next] = true;20                    queue.add(new int[]{u, next, distance + 1});21                }22            }23        }24        return -1;25    }26}

Hints

Hint 1

Can two walks ending at the same vertex have covered different sets of vertices?

Hint 2

Use one bit per visited vertex, and treat (node, mask) as an unweighted search state.

Hint 3

Enqueue every singleton start at distance zero; a move unions the neighbor bit with the mask. Return the first full-mask distance.

Edge Cases

A single vertex returns zero immediately, even with an empty adjacency list.
A star needs repeated visits to its center; for n vertices with at least two leaves the answer is 2n - 4.
A complete 12-vertex graph exercises many states, but all masks fit safely into 32-bit bitwise operations.

Common Mistakes and Interview Tips

Marking only a vertex as seen drops necessary states with a different visited set.
Rejecting moves to already visited vertices incorrectly demands a Hamiltonian path.
Starting only at vertex zero can produce a longer answer; in the star, starting at its center costs five edges.
Using JavaScript shift() on the queue repeatedly adds array movement; use the head index shown.

Key Takeaway

When future choices depend on a small visited subset, expand the graph state to include that subset. Cyclic transitions within a mask need shortest-path exploration rather than assuming subset size alone orders the DP.