Skip to main content
Talentd

Shortest Path Visiting All Nodes - Solution & Explanation

HardDynamic ProgrammingBit ManipulationBreadth-First SearchGraph13 min readAsked at: Amazon, Microsoft, Meta +1
Practice this problem

Problem Statement

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.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.

Approach Overview

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.

Approach 1: Bitmask DP and BFS

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.

Code

PythonJavaJavaScriptCC++C#

Python

Java

JavaScript

C

C++

C#

Complexity

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.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS / Backtracking ExplorationO(n!) (approx)O(n)Conceptual understanding of exploring graph paths; impractical for real constraints
BFS with Bitmask StateO(n * 2^n)O(n * 2^n)Optimal approach for visiting all nodes in small graphs using state compression

Video Solution

Shortest Path Visiting All Nodes | Leetcode 847 | Live coding session 🔥🔥 | BFS + Bit Manipulation • Coding Decoded • 23,514 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Shortest Path Visiting All Nodes easy or hard?
Shortest Path Visiting All Nodes is classified as a Hard problem on LeetCode. The difficulty comes from modeling the problem as BFS over an expanded state space using bitmask dynamic programming rather than a standard graph traversal.
Shortest Path Visiting All Nodes Python/Java solution
Implement BFS using a queue that stores (node, mask, distance). Initialize the queue with every node as a starting point. Update masks with bit operations and track visited states in a 2D array or set. The same logic works in Python, Java, C++, JavaScript, and C#.
How to solve Shortest Path Visiting All Nodes in O(n * 2^n)?
Represent the state as (node, visitedMask) and run multi‑source BFS starting from every node. Update the mask when visiting neighbors using bit operations. Stop when the mask equals (1 << n) - 1, meaning all nodes have been visited. BFS ensures the first such state gives the minimum path length.
What is the best approach for Shortest Path Visiting All Nodes?
Breadth‑First Search with bitmask state compression is the most effective approach. Each state stores the current node and a bitmask representing visited nodes. BFS guarantees the shortest path while the bitmask efficiently tracks visited sets. The complexity is O(n * 2^n) time and space.
Is Shortest Path Visiting All Nodes asked at Google/Amazon/Meta?
Graph state compression and bitmask BFS problems appear in interviews at companies like Google, Amazon, and Meta. This specific LeetCode problem is a classic example used to evaluate graph traversal combined with dynamic programming over subsets.
What data structure is used in Shortest Path Visiting All Nodes?
The solution primarily uses a queue for Breadth‑First Search, a bitmask integer to represent visited nodes, and a visited state table or set to avoid revisiting the same (node, mask) pair. These structures allow efficient exploration of the graph state space.
What is the time complexity of Shortest Path Visiting All Nodes?
The optimal BFS with bitmask solution runs in O(n * 2^n) time. There are at most n * 2^n unique states because each node can appear with any subset of visited nodes. Each state processes its neighbors once during BFS traversal.

Ready to solve this problem?

Practice Shortest Path Visiting All Nodes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find the Minimum Cost Array Permutation