Shortest Path Visiting All Nodes
Given a connected undirected graph with at most 12 nodes, find the length of the shortest walk that visits every node at least once. You may start at any node and revisit nodes and edges.
- 1 ≤ n ≤ 12
- The graph is connected
- n ≤ 12 invites a bitmask over visited nodes
- State = (current node, set of visited nodes)
- Unit edge costs → BFS over the state space
BFS explores in rings of increasing distance, so the first time it reaches a node it has found a shortest path in terms of edge count. "Minimum number of moves" on any state space where each move costs 1 is BFS, whether the states are grid cells, words, or puzzle configurations.
Define a state as (node, mask) where mask records which nodes have been visited. Start BFS simultaneously from every node with its own bit set. From (u, mask) move to each neighbour v producing (v, mask | (1 << v)), skipping states already seen. The first state whose mask is all ones is reached at the minimum number of steps because BFS explores states in distance order.
- Bitmask DP
dp[mask][v]filled in increasing mask order with all-pairs shortest paths is equivalent but harder to write. Brute-force permutations are O(n!).