# Shortest Path Visiting All Nodes
**Difficulty:** HARD
[External](https://leetcode.com/problems/shortest-path-visiting-all-nodes)
Canonical: https://scaleengineer.com/dsa/problems/shortest-path-visiting-all-nodes
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Graph
---
## Problem
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:**

![](https://assets.glich.co/dsa/shortest-path-visiting-all-nodes/image0.jpg) 

**Input:** graph = [[1,2,3],[0],[0],[0]]
**Output:** 4
**Explanation:** One possible path is [1,0,2,0,3]

**Example 2:**

![](https://assets.glich.co/dsa/shortest-path-visiting-all-nodes/image1.jpg) 

**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.length`
* `1 <= n <= 12`
* `0 <= graph[i].length < n`
* `graph[i]` does not contain `i`.
* If `graph[a]` contains `b`, then `graph[b]` contains `a`.
* The input graph is always connected.

# Approaches
## Brute-Force with All Permutations
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.
**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.
**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 `n` can be up to 12, as `12!` is a very large number.
### Explanation
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.
### 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 the `n` nodes. This results in a distance matrix `dist[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.

## Dynamic Programming on Subsets
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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)` using `n` BFS 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 by `mask` and ending at node `u`. Initialize `dp` with a large value. The base cases are `dp[1 << i][i] = 0` for all nodes `i`, representing a path of length 0 starting and ending at `i`.
- **Step 3: DP Transitions**: Iterate through all masks from 1 to `(1 << n) - 1`. For each `mask`, iterate through each node `u` in the `mask`. The value `dp[mask][u]` is updated by considering all possible previous nodes `v` in 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 all `i` from `0` to `n-1`, as the path can end at any node.

## Breadth-First Search on 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.
**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.
**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 of `n <= 12`.
### Explanation
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.

```java
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
    }
}
```
### Algorithm
- **State Representation**: Define a state as a tuple `(currentNode, visitedMask)`, where `currentNode` is the current node and `visitedMask` is a bitmask of visited nodes.
- **Initialization**: Since the path can start at any node, initialize a queue with `n` states: `(i, 1 << i)` for each node `i`. Also, use a 2D boolean array `visited[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 neighbor `v` of `u`, create a new state `(v, newMask)` where `newMask = 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 where `mask` has 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.

# Solutions
### Java

```java
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});
          }
        }
      }
    }
  }
}

```

### CPP

```cpp
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);
          }
        }
      }
    }
  }
};

```

### Python

```python
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 += 1

```