Shortest Path Visiting All Nodes solution and explanation
Google
9 more videos on this problem
Shortest Path Visiting All Nodes | Leetcode 847 | Live coding session 🔥🔥 | BFS + Bit ManipulationCoding Decoded · 13:49 · 23K views
Shortest Path Visiting All Nodes - Leetcode 847 - PythonAdam Djellouli · 28:57 · 18K views
Shortest Path Visiting All Nodes | Leetcode 847 | BFS | Day-26Ayushi Sharma · 34:40 · 11K views
847. Shortest Path Visiting All Nodes (Leetcode Hard)Programming Live with Larry · 30:06 · 3K views
Daily Leetcode #697: Feb 26, 2022 - 847. Shortest Path Visiting All NodesProgramming Live with Larry · 22:44 · 2K views
Shortest Path Visiting All NodesNot A Boring Developer · 4:17 · 1K views
Leetcode 847. Shortest Path Visiting All NodesElite Code · 31:49 · 1K views
Daily Leetcode #1265: Sep 17, 2023 - 847. Shortest Path Visiting All NodesProgramming Live with Larry · 21:16 · 1K views
Shortest Path Visiting All Nodes | Leetcode 847 | BFS | Graph | BitMask | DPNitesh Nanda · 28:27 · 1K views
Shortest Path Visiting All Nodes - LeetCode 847 - PythonAlpha-Code · 24:05 · 711 views
The 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:
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.
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.
from collections import deque
def shortestPathLength(graph):
n = len(graph)
queue = deque()
seen = [[False] * (1 << n) for _ in range(n)]
for i in range(n):
queue.append((i, 1 << i, 0))
seen[i][1 << i] = True
while queue:
node, visited, dist = queue.popleft()
if visited == (1 << n) - 1:
return dist
for neighbor in graph[node]:
new_visited = visited | (1 << neighbor)
if not seen[neighbor][new_visited]:
seen[neighbor][new_visited] = True
queue.append((neighbor, new_visited, dist + 1))
return -1import java.util.*;
public class Solution {
public int shortestPathLength(int[][] graph) {
int n = graph.length;
Queue<int[]> queue = new LinkedList<>();
boolean[][] seen = new boolean[n][1 << n];
for (int i = 0; i < n; i++) {
queue.offer(new int[]{i, 1 << i, 0});
seen[i][1 << i] = true;
}
while (!queue.isEmpty()) {
int[] element = queue.poll();
int node = element[0], visited = element[1], dist = element[2];
if (visited == (1 << n) - 1) {
return dist;
}
for (int neighbor : graph[node]) {
int newVisited = visited | (1 << neighbor);
if (!seen[neighbor][newVisited]) {
queue.offer(new int[]{neighbor, newVisited, dist + 1});
seen[neighbor][newVisited] = true;
}
}
}
return -1;
}
}#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int shortestPathLength(vector<vector<int>>& graph) {
int n = graph.size();
queue<tuple<int, int, int>> q;
vector<vector<bool>> seen(n, vector<bool>(1 << n, false));
for (int i = 0; i < n; i++) {
q.emplace(i, 1 << i, 0);
seen[i][1 << i] = true;
}
while (!q.empty()) {
auto [node, visited, dist] = q.front();
q.pop();
if (visited == (1 << n) - 1) {
return dist;
}
for (int neighbor : graph[node]) {
int newVisited = visited | (1 << neighbor);
if (!seen[neighbor][newVisited]) {
seen[neighbor][newVisited] = true;
q.emplace(neighbor, newVisited, dist + 1);
}
}
}
return -1;
}var shortestPathLength = function(graph) {
const n = graph.length;
const queue = [];
const seen = Array.from({length: n}, () => Array(1 << n).fill(false));
for (let i = 0; i < n; i++) {
queue.push([i, 1 << i, 0]);
seen[i][1 << i] = true;
}
while (queue.length > 0) {
const [node, visited, dist] = queue.shift();
if (visited === (1 << n) - 1) {
return dist;
}
for (const neighbor of graph[node]) {
const newVisited = visited | (1 << neighbor);
if (!seen[neighbor][newVisited]) {
queue.push([neighbor, newVisited, dist + 1]);
seen[neighbor][newVisited] = true;
}
}
}
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_N 12
#define MAX_STATE (1<<MAX_N)
int shortestPathLength(int** graph, int graphSize, int* graphColSize) {
int queue[MAX_N * MAX_STATE][3];
int front = 0, rear = 0;
bool seen[MAX_N][MAX_STATE] = {{false}};
for (int i = 0; i < graphSize; i++) {
queue[rear][0] = i;
queue[rear][1] = 1 << i;
queue[rear][2] = 0;
rear++;
seen[i][1 << i] = true;
}
while (front < rear) {
int *top = queue[front++];
int node = top[0], visited = top[1], dist = top[2];
if (visited == (1 << graphSize) - 1) {
return dist;
}
for (int j = 0; j < graphColSize[node]; j++) {
int neighbor = graph[node][j];
int newVisited = visited | (1 << neighbor);
if (!seen[neighbor][newVisited]) {
queue[rear][0] = neighbor;
queue[rear][1] = newVisited;
queue[rear][2] = dist + 1;
rear++;
seen[neighbor][newVisited] = true;
}
}
}
return -1;
}using System;
using System.Collections.Generic;
public class Solution {
public int ShortestPathLength(int[][] graph) {
int n = graph.Length;
Queue<(int, int, int)> queue = new Queue<(int, int, int)>();
bool[,] seen = new bool[n, 1 << n];
for (int i = 0; i < n; i++) {
queue.Enqueue((i, 1 << i, 0));
seen[i, 1 << i] = true;
}
while (queue.Count > 0) {
var (node, visited, dist) = queue.Dequeue();
if (visited == (1 << n) - 1) {
return dist;
}
for (int j = 0; j < graph[node].Length; j++) {
int neighbor = graph[node][j];
int newVisited = visited | (1 << neighbor);
if (!seen[neighbor, newVisited]) {
queue.Enqueue((neighbor, newVisited, dist + 1));
seen[neighbor, newVisited] = true;
}
}
}
return -1;
}
}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 2: Default Approach
function shortestPathLength(graph: number[][]): number {
const n = graph.length;
const q: number[][] = [];
const vis: boolean[][] = new Array(n).fill(false).map(() => new Array(1 << n).fill(false));
for (let i = 0; i < n; ++i) {
q.push([i, 1 << i]);
vis[i][1 << i] = true;
}
for (let ans = 0; ; ++ans) {
for (let k = q.length; k; --k) {
const [i, st] = q.shift()!;
if (st === (1 << n) - 1) {
return ans;
}
for (const j of graph[i]) {
const nst = st | (1 << j);
if (!vis[j][nst]) {
vis[j][nst] = true;
q.push([j, nst]);
}
}
}
}
}func shortestPathLength(graph [][]int) int {
n := len(graph)
q := [][2]int{}
vis := make([][]bool, n)
for i := range vis {
vis[i] = make([]bool, 1<<n)
vis[i][1<<i] = true
q = append(q, [2]int{i, 1 << i})
}
for ans := 0; ; ans++ {
for k := len(q); k > 0; k-- {
p := q[0]
q = q[1:]
i, st := p[0], p[1]
if st == (1<<n)-1 {
return ans
}
for _, j := range graph[i] {
nst := st | 1<<j
if !vis[j][nst] {
vis[j][nst] = true
q = append(q, [2]int{j, nst})
}
}
}
}
}use std::collections::VecDeque;
impl Solution {
#[allow(dead_code)]
pub fn shortest_path_length(graph: Vec<Vec<i32>>) -> i32 {
let n = graph.len();
let mut vis = vec![vec![false; 1 << n]; n];
let mut q = VecDeque::new();
// Initialize the queue
for i in 0..n {
q.push_back(((i, 1 << i), 0));
vis[i][1 << i] = true;
}
// Begin BFS
while !q.is_empty() {
let ((i, st), count) = q.pop_front().unwrap();
if st == (1 << n) - 1 {
return count;
}
// If the path has not been visited
for j in &graph[i] {
let nst = st | (1 << *j);
if !vis[*j as usize][nst] {
q.push_back(((*j as usize, nst), count + 1));
vis[*j as usize][nst] = true;
}
}
}
-1
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
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.