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 contain i.graph[a] contains b, then graph[b] contains a.Problem Overview: You are given an undirected connected graph and need the minimum number of steps required to visit every node at least once. You can start from any node and revisit nodes or edges if needed, but the goal is to minimize the total path length.
Approach 1: Brute Force DFS / Backtracking (Exponential Time)
A naive strategy tries every possible path using depth‑first search and keeps track of which nodes have been visited. Each recursive call explores all neighbors while maintaining a visited set. Because nodes can be revisited and the order of visiting matters, the number of possible paths grows extremely fast. The time complexity is roughly O(n!) or worse depending on graph structure, with O(n) recursion space. This approach mainly helps build intuition about exploring graph paths but becomes infeasible even for small graphs.
Approach 2: BFS with Bitmask State Compression (O(n * 2^n))
The optimal solution models the problem as a shortest path search on an expanded state space. Instead of tracking only the current node, the state becomes (node, mask) where mask is a bitmask representing which nodes have been visited. A bit i in the mask is set if node i has already been visited. This compresses the visited set into an integer and allows efficient transitions.
Initialize a multi‑source Breadth‑First Search by pushing every node into the queue with its own mask (1 << node). BFS expands level by level, ensuring the first time we reach a state where the mask equals (1 << n) - 1 (all nodes visited) is the shortest path length. For each step, iterate through the current node’s neighbors and update the mask using nextMask = mask | (1 << neighbor). A visited structure prevents revisiting the same (node, mask) pair.
This approach combines ideas from bitmask state compression and shortest path search in graphs. The number of states is n * 2^n, and each edge transition is processed once per state. Time complexity is O(n * 2^n) and space complexity is also O(n * 2^n) due to the visited state table and queue.
The same concept can also be interpreted as a dynamic programming over subsets problem similar to Traveling Salesman. The BFS formulation is usually simpler because it directly computes the shortest number of edges while implicitly performing dynamic programming over bitmask states.
Recommended for interviews: BFS with bitmask state compression is the expected solution. It demonstrates understanding of graph traversal, state compression, and shortest path modeling. Mentioning the brute force exploration first shows problem analysis, but implementing the BFS + bitmask approach shows strong algorithmic skill.
This approach uses a combination of Dynamic Programming (DP) with a Bitmask to represent the set of nodes visited and Breadth First Search (BFS) to explore the graph.
Each state can be defined by a tuple (current_node, visited_nodes), where current_node is the current node, and visited_nodes is a bitmask representing which nodes have been visited.
The goal is to find the shortest path when visited_nodes has every node set (i.e., all nodes visited). We explore the states using BFS until we find the goal state.
We use a queue to perform a BFS while keeping track of visited nodes using a bitmask. The queue stores tuples (node, visited, distance). Initialize the queue with all nodes and their respective visited state. For each node, check if all nodes are visited; if so, return the current distance as it represents the shortest path.
Time Complexity is O(n * 2^n) due to the exploration of states (node and visited set), and Space Complexity is O(n*2^n) for visited states storage.
| Approach | Complexity |
|---|---|
| Bitmask DP and BFS | Time Complexity is O(n * 2^n) due to the exploration of states (node and visited set), and Space Complexity is O(n*2^n) for visited states storage. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS / Backtracking Exploration | O(n!) (approx) | O(n) | Conceptual understanding of exploring graph paths; impractical for real constraints |
| BFS with Bitmask State | O(n * 2^n) | O(n * 2^n) | Optimal approach for visiting all nodes in small graphs using state compression |
Shortest Path Visiting All Nodes | Leetcode 847 | Live coding session 🔥🔥 | BFS + Bit Manipulation • Coding Decoded • 23,108 views views
Watch 9 more video solutions →Practice Shortest Path Visiting All Nodes with our built-in code editor and test cases.
Practice on FleetCode