Code Implementation

from collections import deque

class Solution:
    def shortestPathLength(self, graph):
        n = len(graph)
        target = (1 << n) - 1  # All nodes visited mask
        queue = deque((i, 1 << i) for i in range(n))
        visited = set((i, 1 << i) for i in range(n))
        steps = 0

        while queue:
            for _ in range(len(queue)):
                node, mask = queue.popleft()
                if mask == target:
                    return steps
                for nei in graph[node]:
                    next_mask = mask | (1 << nei)
                    if (nei, next_mask) not in visited:
                        visited.add((nei, next_mask))
                        queue.append((nei, next_mask))
            steps += 1
        return -1
      

#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        int target = (1 << n) - 1;
        queue<pair<int, int>> q;
        vector<vector<bool>> visited(n, vector<bool>(1 << n, false));
        for (int i = 0; i < n; ++i) {
            q.push({i, 1 << i});
            visited[i][1 << i] = true;
        }
        int steps = 0;
        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; ++i) {
                auto [node, mask] = q.front(); q.pop();
                if (mask == target) return steps;
                for (int nei : graph[node]) {
                    int next_mask = mask | (1 << nei);
                    if (!visited[nei][next_mask]) {
                        visited[nei][next_mask] = true;
                        q.push({nei, next_mask});
                    }
                }
            }
            steps++;
        }
        return -1;
    }
};
      

import java.util.*;

class Solution {
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        int target = (1 << n) - 1;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][1 << n];
        for (int i = 0; i < n; i++) {
            queue.offer(new int[]{i, 1 << i});
            visited[i][1 << i] = true;
        }
        int steps = 0;
        while (!queue.isEmpty()) {
            int sz = queue.size();
            for (int i = 0; i < sz; i++) {
                int[] curr = queue.poll();
                int node = curr[0], mask = curr[1];
                if (mask == target) return steps;
                for (int nei : graph[node]) {
                    int nextMask = mask | (1 << nei);
                    if (!visited[nei][nextMask]) {
                        visited[nei][nextMask] = true;
                        queue.offer(new int[]{nei, nextMask});
                    }
                }
            }
            steps++;
        }
        return -1;
    }
}
      

/**
 * @param {number[][]} graph
 * @return {number}
 */
var shortestPathLength = function(graph) {
    const n = graph.length;
    const target = (1 << n) - 1;
    const queue = [];
    const visited = Array.from({length: n}, () => Array(1 << n).fill(false));
    for (let i = 0; i < n; i++) {
        queue.push([i, 1 << i]);
        visited[i][1 << i] = true;
    }
    let steps = 0;
    while (queue.length) {
        let sz = queue.length;
        for (let i = 0; i < sz; i++) {
            let [node, mask] = queue.shift();
            if (mask === target) return steps;
            for (let nei of graph[node]) {
                let nextMask = mask | (1 << nei);
                if (!visited[nei][nextMask]) {
                    visited[nei][nextMask] = true;
                    queue.push([nei, nextMask]);
                }
            }
        }
        steps++;
    }
    return -1;
};
      

Problem Description

Given an undirected, connected graph represented as an adjacency list graph where graph[i] contains all the nodes connected to node i, your goal is to find the length of the shortest path that visits every node at least once. You can start and stop at any node, and you may revisit nodes and edges as needed. The key constraints are:

• Each node must be visited at least once.
• You may revisit nodes and edges.
• The input graph is connected and undirected.
• Return the minimal number of steps (edges traversed) required to visit all nodes.

Thought Process

At first glance, this problem resembles the Traveling Salesman Problem (TSP), where the goal is to visit every node in a graph. However, the key differences are:

• You can start and end at any node.
• You may revisit nodes and edges.

Solution Approach

The solution uses BFS with state compression via bitmasking. Here's a step-by-step breakdown:

1. State Representation:
   • Each state is a pair: (current_node, visited_mask).
   • visited_mask is an integer where the i-th bit is 1 if node i has been visited.
2. Initialization:
   • Start BFS from every node, each with a mask that has only that node set as visited.
   • Add all these starting states to the BFS queue and mark them as visited.
3. BFS Traversal:
   • At each step, dequeue a state (node, mask).
   • If mask has all bits set (i.e., all nodes visited), return the current number of steps.
   • For each neighbor, create a new state with the neighbor as the current node and update the mask to include the neighbor.
   • If this new state has not been visited, enqueue it and mark as visited.
4. Termination:
   • The first time we reach a state where all nodes have been visited, we have found the shortest path (since BFS guarantees minimal steps).

• The number of possible states is n * 2^n (n nodes, 2^n possible masks), which is manageable for n ≤ 12.
• Using a visited set prevents redundant exploration.

Example Walkthrough

Let's walk through a sample input:

Input: graph = [[1,2,3],[0],[0],[0]]
This means:

• Node 0 is connected to nodes 1, 2, 3.
• Nodes 1, 2, 3 are only connected to node 0.

1. Initialize BFS from each node with only that node visited.
2. At step 0: States = (0, 0001), (1, 0010), (2, 0100), (3, 1000)
3. At step 1: From node 0, can go to 1, 2, 3, updating the mask each time (e.g., (1, 0011), (2, 0101), (3, 1001)). From nodes 1, 2, 3, can only go to node 0.
4. At step 2: Continue expanding states. Eventually, reach a state where all bits in the mask are 1 (i.e., 1111 = 15), meaning all nodes have been visited.
5. The shortest path length found is 4.

Time and Space Complexity

Brute-force Approach:

• Would try all permutations of node visits: O(n!), which is infeasible for large n.

• There are n * 2^n possible states (n nodes, each with 2^n masks).
• Each state is processed at most once, and each edge is traversed for each state.
• Time Complexity: O(n^2 * 2^n), because each node can have up to n neighbors and there are 2^n masks.
• Space Complexity: O(n * 2^n) for the visited set and queue.

Summary

The "Shortest Path Visiting All Nodes" problem is efficiently solved by combining BFS with bitmasking to represent visited nodes. By treating each pair of (current node, visited mask) as a unique state and using BFS to explore all possible paths, we guarantee finding the shortest path that visits every node. The use of bitmasking keeps the solution efficient and elegant, avoiding redundant work and ensuring that the first time all nodes are visited, we have found the optimal answer.