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.
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}); } } } } }}Video 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.