We need to find the shortest path (fewest edges) that visits every node in an undirected graph. There are a few things that make this different from typical shortest path problems.

First, we can start at any node. There's no fixed source. Second, we can revisit nodes and reuse edges. This is critical because the graph might not have a Hamiltonian path (a path that visits every node exactly once), so backtracking through already-visited nodes might be necessary. Third, "shortest" means fewest edges traversed, not fewest unique nodes.

The challenge is tracking which nodes we've visited along the way. A plain BFS over nodes does not work, because the state isn't only the current position. Two paths that arrive at the same node but have visited different subsets of nodes are different states with different remaining work. The state therefore has to combine where we are with what we've already visited. That definition drives every approach to this problem.

Key Constraints:

Intuition

Try every order in which the nodes could be visited and keep the shortest walk that covers all of them. Start from each node in turn and use backtracking to explore the next moves: at each step move to a neighbor, either an unvisited one or a visited one used as a stepping stone toward an unvisited node. When every node has been visited, record the number of edges taken.

This enumerates walks directly, so it is expensive, but it states exactly what we are minimizing: the number of edges in a walk that touches all n nodes.

Because a walk may pass through already-visited nodes, the search needs a bound, otherwise it can cycle between two adjacent nodes forever. A spanning-tree DFS of a connected graph visits every node using at most 2(n-1) edges, so the answer is never larger than that. Seeding the best-so-far with 2(n-1) gives a valid upper bound and lets the edges >= best prune cut off any branch that has already used that many edges without finishing.

Algorithm

Example Walkthrough

Input:

The graph is a star: node 0 is the center, connected to 1, 2, and 3, which are leaves.

We try each starting node. Starting at node 0 (visitedCount=1), we can reach 1, 2, 3 in turn but must return to 0 between leaves, so the walk 0->1->0->2->0->3 takes 6 edges. Starting at a leaf is better. Starting at node 1: 1->0 (visit 0, count 2), 0->2 (visit 2, count 3), 2->0 (move through a visited node, count still 3, edges now 3), 0->3 (visit 3, count 4 = n). That walk is 1,0,2,0,3 with 4 edges. The edges >= minPath prune then cuts off any branch that has already used 4 or more edges without finishing, which is what keeps the search from looping through visited nodes forever. The minimum over all starting nodes is 4.

Code

Backtracking re-derives the same (current node, visited set) combination over and over, because it has no memory of states it already reached by a shorter walk. The next approach gives each distinct state a single best distance and visits it once.

Redefine the state. In ordinary BFS on a graph, the state is the current node. Here, a path that has visited {0, 1, 2} and one that has visited {0, 1, 3} face different remaining work even if both currently sit on the same node, so both pieces of information belong in the state.

The state becomes a pair: (current node, set of visited nodes). With n ≤ 12, the visited set fits in a bitmask where bit i is set when node i has been visited. That gives at most n 2^n states, which for n=12 is 12 4096 = 49,152.

Run BFS over this state space. Because BFS expands states in order of increasing distance, the first time it reaches a state whose mask has all bits set, that distance is the shortest path length.

Since we can start at any node, we seed the BFS queue with all n starting states: (node i, bitmask with only bit i set) for each node i. The target is any state where the bitmask equals (1 << n) - 1, meaning all n bits are on.

Algorithm

Example Walkthrough

Code

The BFS over states is efficient on its own. A dynamic programming formulation solves the same problem from a different angle, separating the shortest distance between nodes from the order in which to visit them.

Intuition

The state is again (current node, visited mask), but instead of expanding distance by distance, this approach builds up answers from smaller visited sets to larger ones.

Define dp[mask][i] as the minimum number of edges in a walk that has visited exactly the nodes in mask and currently sits on node i. The answer is the minimum of dp[fullMask][i] across all nodes i.

The base case: dp[1 << i][i] = 0 for every node i, since starting at node i with only node i marked costs 0 edges.

The transition relies on a precomputed all-pairs shortest distance dist[i][j]. From state (mask, i), moving on to a node j not yet in mask costs dp[mask][i] + dist[i][j], and lands in state (mask | (1 << j), j). The value dist[i][j] already includes any edges spent passing through other nodes to get from i to j, which is why the DP can treat "go to the next new node" as a single weighted step.

The decomposition splits the work in two: the all-pairs BFS answers "what is the shortest way from A to B?", and the bitmask DP answers "in what order should the nodes be visited?".

Algorithm

Example Walkthrough

Code