Shortest Path Visiting All Nodes
HardPrompt
You have an undirected, connected graph of n nodes labeled from 0 to n - 1. You are given an array graph where graph[i] is a list of all the nodes connected with node i by an edge.
Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.
Example 1:
Input: graph = [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]Example 2:
Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]
Constraints:
n == graph.length1 <= n <= 120 <= graph[i].length < ngraph[i]does not containi.- If
graph[a]containsb, thengraph[b]containsa. - The input graph is always connected.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach treats the problem as a classic Traveling Salesperson Problem (TSP). The core idea is to try every possible path that visits all nodes and find the shortest one. This is done by first pre-calculating the shortest distances between all pairs of nodes and then checking every permutation of nodes to find the one that results in the minimum total path length.
Algorithm
- Step 1: All-Pairs Shortest Paths (APSP): First, compute the shortest distance between every pair of nodes
(u, v)in the graph. Since all edge weights are 1, this can be done by running a Breadth-First Search (BFS) starting from each of thennodes. This results in a distance matrixdist[n][n]. - Step 2: Generate Permutations: Generate all
n!possible orderings (permutations) of the nodes(0, 1, ..., n-1). - Step 3: Calculate Path Length: For each permutation
p = (p_0, p_1, ..., p_{n-1}), calculate the total length of the path that visits nodes in this specific order. The length is the sum of distances between consecutive nodes in the permutation:dist(p_0, p_1) + dist(p_1, p_2) + ... + dist(p_{n-2}, p_{n-1}). - Step 4: Find Minimum: Keep track of the minimum path length found across all permutations. This minimum value is the result.
Walkthrough
The brute-force method involves two main stages. First, we need to know the shortest way to get from any node to any other node. We can build a distance matrix by running a BFS from every single node. Once we have this dist[i][j] matrix, the problem is transformed into finding an ordering of nodes p_0, p_1, ..., p_{n-1} that minimizes the sum of dist(p_i, p_{i+1}). We can find this optimal ordering by generating all n! permutations of the nodes, calculating the path length for each, and selecting the minimum. While conceptually straightforward, this method is computationally explosive.
Complexity
Time
O(n^3 + n * n!) The all-pairs shortest path calculation using `n` BFS runs takes `O(n * (n + E))` which is at most `O(n^3)`. Generating and evaluating all `n!` permutations takes `O(n * n!)` time. The factorial term dominates, making this approach impractical.
Space
O(n^2) This space is required to store the all-pairs shortest path distance matrix.
Trade-offs
Pros
Conceptually simple to understand if familiar with the Traveling Salesperson Problem.
Cons
Extremely inefficient due to the
O(n!)complexity.Not feasible for the given constraints where
ncan be up to 12, as12!is a very large number.
This approach uses dynamic programming with bitmasking to solve the problem efficiently, avoiding the n! complexity of brute force. It still frames the problem as a TSP variant. A DP state dp[mask][u] is used to keep track of the shortest path visiting a subset of nodes (mask) and ending at a particular node (u). By building up solutions for larger subsets from smaller ones, we can find the overall shortest path.
Algorithm
- Step 1: All-Pairs Shortest Paths (APSP): Similar to the brute-force approach, pre-compute the shortest distance
dist(u, v)between all pairs of nodes(u, v)usingnBFS runs. - Step 2: DP State and Initialization: Define a 2D DP array,
dp[mask][u], to store the length of the shortest path visiting the set of nodes represented bymaskand ending at nodeu. Initializedpwith a large value. The base cases aredp[1 << i][i] = 0for all nodesi, representing a path of length 0 starting and ending ati. - Step 3: DP Transitions: Iterate through all masks from 1 to
(1 << n) - 1. For eachmask, iterate through each nodeuin themask. The valuedp[mask][u]is updated by considering all possible previous nodesvin the path:dp[mask][u] = min(dp[mask][u], dp[mask_without_u][v] + dist[v][u]). - Step 4: Final Result: After filling the DP table, the answer is the minimum value among
dp[(1 << n) - 1][i]for allifrom0ton-1, as the path can end at any node.
Walkthrough
This method is a standard DP solution for the Traveling Salesperson Problem. We first compute all-pairs shortest paths to get dist[i][j]. Then, we build a DP table dp[mask][u]. The mask is an integer where the i-th bit is 1 if node i has been visited, and 0 otherwise. u is the last node visited in the path. We iterate through masks, typically in increasing order of the number of set bits. For each state (mask, u), we find the minimum path length by trying all possible predecessors v from the subproblem (mask without u, v) and adding the distance dist[v][u]. The final answer is the minimum path length over all states where all nodes have been visited.
import java.util.Arrays;import java.util.LinkedList;import java.util.Queue; class Solution { public int shortestPathLength(int[][] graph) { int n = graph.length; if (n <= 1) return 0; int[][] dist = new int[n][n]; for (int i = 0; i < n; i++) { Arrays.fill(dist[i], -1); Queue<int[]> q = new LinkedList<>(); q.offer(new int[]{i, 0}); dist[i][i] = 0; while (!q.isEmpty()) { int[] curr = q.poll(); int u = curr[0]; int d = curr[1]; for (int v : graph[u]) { if (dist[i][v] == -1) { dist[i][v] = d + 1; q.offer(new int[]{v, d + 1}); } } } } int[][] dp = new int[1 << n][n]; for (int[] row : dp) { Arrays.fill(row, n * n); } for (int i = 0; i < n; i++) { dp[1 << i][i] = 0; } for (int mask = 1; mask < (1 << n); mask++) { for (int u = 0; u < n; u++) { if ((mask & (1 << u)) != 0) { int prevMask = mask ^ (1 << u); if (prevMask == 0) continue; for (int v = 0; v < n; v++) { if ((prevMask & (1 << v)) != 0) { dp[mask][u] = Math.min(dp[mask][u], dp[prevMask][v] + dist[v][u]); } } } } } int minLength = Integer.MAX_VALUE; int finalMask = (1 << n) - 1; for (int i = 0; i < n; i++) { minLength = Math.min(minLength, dp[finalMask][i]); } return minLength; }}Complexity
Time
O(n^3 + n^2 * 2^n) The APSP pre-computation takes `O(n^3)`. The DP calculation involves three nested loops over masks, `u`, and `v`, resulting in `O(2^n * n * n)` complexity.
Space
O(n * 2^n) This is dominated by the `dp` table of size `(1 << n) * n`. The `dist` matrix adds `O(n^2)` space.
Trade-offs
Pros
Significantly more efficient than brute-force, with a complexity of
O(n^2 * 2^n).A standard and powerful technique for this class of problems.
Cons
Requires an
O(n^3)pre-computation step for the all-pairs shortest paths, which can be avoided.The logic can be more complex to implement compared to a direct BFS on the state space.
This approach is the most efficient and direct way to solve the problem. It uses Breadth-First Search (BFS), which is ideal for finding the shortest path in an unweighted graph. We perform the BFS not on the graph nodes themselves, but on a state space where each state consists of the current node and a bitmask of all nodes visited so far. This elegantly handles the problem's constraints, including revisiting nodes and starting/ending anywhere.
Algorithm
- State Representation: Define a state as a tuple
(currentNode, visitedMask), wherecurrentNodeis the current node andvisitedMaskis a bitmask of visited nodes. - Initialization: Since the path can start at any node, initialize a queue with
nstates:(i, 1 << i)for each nodei. Also, use a 2D boolean arrayvisited[node][mask]to keep track of visited states to avoid redundant computations. - BFS Traversal: Perform a level-order BFS. In each step, dequeue a state
(u, mask). For each neighborvofu, create a new state(v, newMask)wherenewMask = mask | (1 << v). If this new state has not been visited, mark it as visited and enqueue it. - Termination: The BFS explores paths of increasing length. The first time a state
(u, mask)is reached wheremaskhas all bits set (i.e.,mask == (1 << n) - 1), we have found a shortest path. The current level of the BFS (path length) is the answer.
Walkthrough
Instead of pre-calculating distances, this method explores paths step-by-step. A state in our search is (u, mask), representing being at node u having visited the set of nodes in mask. We want the shortest path in terms of edge traversals to reach any state where all nodes are visited.
We can initialize a queue with all possible starting states (i, 1 << i) for i = 0 to n-1. Then, we perform a standard BFS. At each level, we explore all paths that are one edge longer. We use a visited array visited[u][mask] to ensure we process each state only once. The first time we encounter a state where the mask is (1 << n) - 1, we've found the shortest path length, which is simply the current BFS level.
import java.util.Queue;import java.util.LinkedList; class Solution { public int shortestPathLength(int[][] graph) { int n = graph.length; if (n <= 1) { return 0; } int finalMask = (1 << n) - 1; Queue<int[]> queue = new LinkedList<>(); // {node, mask} boolean[][] visited = new boolean[n][1 << n]; // Initialize BFS with all possible starting nodes for (int i = 0; i < n; i++) { int initialMask = 1 << i; queue.offer(new int[]{i, initialMask}); visited[i][initialMask] = true; } int pathLength = 0; while (!queue.isEmpty()) { int levelSize = queue.size(); for (int i = 0; i < levelSize; i++) { int[] currentState = queue.poll(); int u = currentState[0]; int mask = currentState[1]; if (mask == finalMask) { return pathLength; } for (int v : graph[u]) { int newMask = mask | (1 << v); if (!visited[v][newMask]) { visited[v][newMask] = true; queue.offer(new int[]{v, newMask}); } } } pathLength++; } return -1; // Should not be reached as the graph is connected }}Complexity
Time
O(n^2 * 2^n) The number of states is `n * 2^n`. For each state, we iterate through its neighbors (at most `n-1`). This gives a total time complexity of `O(n * 2^n * n)`.
Space
O(n * 2^n) The space is used for the `visited` 2D array and the BFS queue, both of which can store up to `n * 2^n` states.
Trade-offs
Pros
Most efficient approach for the given constraints.
Directly solves the problem without needing a separate pre-computation step like APSP.
BFS is a natural fit for shortest path problems on unweighted graphs.
Cons
The space complexity of
O(n * 2^n)can be large, but it is manageable for the given constraint ofn <= 12.
Solutions
Solution
class Solution {public int shortestPathLength(int[][] graph) { int n = graph.length; Deque<int[]> q = new ArrayDeque<>(); boolean[][] vis = new boolean[n][1 << n]; for (int i = 0; i < n; ++i) { q.offer(new int[]{i, 1 << i}); vis[i][1 << i] = true; } for (int ans = 0;; ++ans) { for (int k = q.size(); k > 0; --k) { var p = q.poll(); int i = p[0], st = p[1]; if (st == (1 << n) - 1) { return ans; } for (int j : graph[i]) { int nst = st | 1 << j; if (!vis[j][nst]) { vis[j][nst] = true; q.offer(new int[]{j, nst}); } } } } }}class Solution {public: int shortestPathLength(vector<vector<int>> &graph) { int n = graph.size(); queue<pair<int, int>> q; bool vis[n][1 << n]; memset(vis, false, sizeof(vis)); for (int i = 0; i < n; ++i) { q.emplace(i, 1 << i); vis[i][1 << i] = true; } for (int ans = 0;; ++ans) { for (int k = q.size(); k; --k) { auto [i, st] = q.front(); q.pop(); if (st == (1 << n) - 1) { return ans; } for (int j : graph[i]) { int nst = st | 1 << j; if (!vis[j][nst]) { vis[j][nst] = true; q.emplace(j, nst); } } } } }};class Solution: def shortestPathLength(self, graph: List[List[int]]) -> int: n = len(graph) q = deque() vis = set() for i in range(n): q . append((i, 1 << i)) vis . add((i, 1 << i)) ans = 0 while 1: for _ in range(len(q)): i, st = q . popleft() if st == (1 << n) - 1: return ans for j in graph[i]: nst = st | 1 << j if (j, nst) not in vis: vis . add((j, nst)) q . append((j, nst)) ans += 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.