Shortest Path Visiting All Nodes - Practice Coding Problems

Shortest Path Visiting All Nodes - 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.

Input & Output

Example 1 — Star Graph

$ Input: graph = [[1,2,3],[0],[0],[0]]

› Output: 4

💡 Note: One shortest path: start at node 0, visit 0→1→0→2→0→3 (path length 4). All nodes are visited.

Example 2 — Linear Graph

$ Input: graph = [[1],[0,2],[1]]

› Output: 2

💡 Note: Shortest path: 0→1→2 or 2→1→0 (path length 2). Visits all 3 nodes.

Example 3 — Single Node

$ Input: graph = [[]]

› Output: 0

💡 Note: Only one node exists, so path length is 0 (already visited all nodes).

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

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Undirected connected graph as adjacency list

Find Path

Find shortest path that visits every node

Output Length

Return the path length (number of edges)

Key Takeaway

🎯 Key Insight: Use BFS with bitmasks to represent visited nodes as states, guaranteeing the shortest path while avoiding exponential path enumeration

Asked in

G Google 25 f Facebook 18 a Amazon 12

The key insight is to use BFS with bitmasks to represent visited node states efficiently. Instead of exploring all path permutations, we track (node, visited_mask) states and use BFS to guarantee the shortest path. Best approach is BFS with Bitmask: Time O(n × 2ⁿ), Space O(n × 2ⁿ).

Common Approaches

Approach	Time	Space	Notes
✓ BFS with Bitmask	O(n × 2ⁿ)	O(n × 2ⁿ)	Use BFS with bitmask to track visited nodes efficiently
Brute Force DFS	O(n! × 2ⁿ)	O(n)	Try all possible paths from every starting node using DFS

BFS with Bitmask — Algorithm Steps

Start BFS from all nodes simultaneously
Use bitmask to represent visited nodes efficiently
Explore neighbors and update visited mask
Return path length when all nodes visited

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize BFS

Start from all nodes with initial bitmask

Explore States

BFS explores (node, visited_mask) combinations

Find Target

Return when all nodes visited (mask = 1111)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STATES 10000

typedef struct {
    int node;
    int mask;
    int pathLength;
} State;

int solution(int** graph, int graphSize, int* graphColSize) {
    if (graphSize == 1) return 0;
    
    State queue[MAX_STATES];
    int visited[20][1024]; // Max 12 nodes, so 2^12 = 4096 states
    memset(visited, 0, sizeof(visited));
    
    int front = 0, rear = 0;
    
    // Start from each node
    for (int i = 0; i < graphSize; i++) {
        int mask = 1 << i;
        queue[rear].node = i;
        queue[rear].mask = mask;
        queue[rear].pathLength = 0;
        rear++;
        visited[i][mask] = 1;
    }
    
    int targetMask = (1 << graphSize) - 1;
    
    while (front < rear) {
        State current = queue[front++];
        
        // Explore neighbors
        for (int i = 0; i < graphColSize[current.node]; i++) {
            int neighbor = graph[current.node][i];
            int newMask = current.mask | (1 << neighbor);
            
            if (newMask == targetMask) {
                return current.pathLength + 1;
            }
            
            if (!visited[neighbor][newMask]) {
                visited[neighbor][newMask] = 1;
                queue[rear].node = neighbor;
                queue[rear].mask = newMask;
                queue[rear].pathLength = current.pathLength + 1;
                rear++;
            }
        }
    }
    
    return -1;
}

int main() {
    // Simple parsing for demo - assumes small input
    int n = 4; // Example size
    int** graph = (int**)malloc(n * sizeof(int*));
    int* graphColSize = (int*)malloc(n * sizeof(int));
    
    // Example graph [[1,2,3],[0],[0],[0]]
    graph[0] = (int*)malloc(3 * sizeof(int));
    graph[0][0] = 1; graph[0][1] = 2; graph[0][2] = 3;
    graphColSize[0] = 3;
    
    graph[1] = (int*)malloc(1 * sizeof(int));
    graph[1][0] = 0;
    graphColSize[1] = 1;
    
    graph[2] = (int*)malloc(1 * sizeof(int));
    graph[2][0] = 0;
    graphColSize[2] = 1;
    
    graph[3] = (int*)malloc(1 * sizeof(int));
    graph[3][0] = 0;
    graphColSize[3] = 1;
    
    printf("%d\n", solution(graph, n, graphColSize));
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(graph[i]);
    }
    free(graph);
    free(graphColSize);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 2ⁿ)

We process each of n nodes for each possible subset of visited nodes (2ⁿ subsets)

✓ Linear Growth

Space Complexity

O(n × 2ⁿ)

Queue stores states and visited array tracks (node, mask) combinations

⚡ Linearithmic Space

89.5K Views

Medium Frequency

~35 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS with Bitmask — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler