Shortest Path Visiting All Nodes
Hard · Graphs · Dynamic Programming · Bit Manipulation · Breadth-First Search · Graph · Bitmask
Problem
You have an undirected, connected graph of n nodes labeled 0 to n - 1, given as an adjacency list graph where graph[i] lists the neighbors of node i.
Return the length (number of edges) of the shortest walk that visits every node at least once. You may start and end at any node, revisit nodes, and reuse edges.
Examples
Input: graph = [[1,2,3],[0],[0],[0]] Output: 4
Start at a leaf: 1-0-2-0-3 is four edges.
Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]] Output: 4
One shortest walk is 0-1-4-2-3.
Input: graph = [[]] Output: 0
The only node is visited at the start.
Constraints
- n == len(graph)
- 1 <= n <= 12
- 0 <= len(graph[i]) < n
- graph[i] does not contain i
- If graph[a] contains b then graph[b] contains a
- The graph is connected
Approaches
- Baseline: all distances, then every visiting order — time O(n! · n + n · (n + m)), space O(n²)
Follow-up
The state space has n · 2^n states, about 49,000 for 12 nodes, which is why n is kept small: the problem is a shortest Hamiltonian-path relative. The use cases ask for a closed walk (a bitmask DP over all-pairs distances) and for visiting only some required nodes from a fixed start.
Related problems
Start free on Cariara · Coding problems · System design studio
