LeetCode Solutions Blog

Shortest Path Visiting All Nodes

Number: 877

Difficulty: Hard

Paid? No

Problem Description

Given an undirected, connected graph of n nodes, where nodes are labeled from 0 to n-1 and graph[i] contains all nodes adjacent to i, find the length of the shortest path that visits every node. You may start and end at any node, revisit nodes, and re-use edges.

Key Insights

The problem is a variant of the Traveling Salesman Problem, but the small constraint (n ≤ 12) permits a solution using bitmasking.
Each state can be represented as a combination of the current node and a bitmask indicating which nodes have been visited.
Breadth-first search (BFS) helps guarantee that the first time we encounter a state with all nodes visited, it is via the shortest path.
Using multi-source BFS from each node as a starting point simplifies the logic because we can start from any node.

Space and Time Complexity

Time Complexity: O(n * 2^n) where n is the number of nodes since we potentially visit each state (node, visited-mask) once. Space Complexity: O(n * 2^n) for storing the states in the visited set and the BFS queue.

Solution

The solution uses a BFS that expands states of the form (current node, visited mask). Initially, every node is added to the queue with its corresponding bitmask. At each BFS step, we iterate over all adjacent nodes and update the visited mask by setting the bit corresponding to the neighbor. When the visited mask equals (1 << n) - 1 (all nodes visited), we return the number of steps taken. This BFS expansion ensures that we always find the shortest path.

Code Solutions

# Import required collections for the queue
from collections import deque

def shortestPathLength(graph):
    n = len(graph)
    # If there is only one node, we're already done
    if n == 1:
        return 0
    
    # All nodes visited bitmask (e.g., for n=3, all_visited = 0b111)
    all_visited = (1 << n) - 1
    
    # Creating a queue for BFS where each element is (current_node, visited_mask)
    queue = deque()
    # Use a set to record visited (node, mask) states
    seen = set()
    
    # Multi-source initialization: start from every node.
    for i in range(n):
        # visited_mask with only the i-th bit set
        mask = 1 << i
        queue.append((i, mask, 0))  # (node, visited_mask, distance)
        seen.add((i, mask))
    
    # BFS loop
    while queue:
        node, mask, dist = queue.popleft()
        # Check all adjacent nodes
        for neighbor in graph[node]:
            # Update the visited mask with the neighbor visited
            next_mask = mask | (1 << neighbor)
            # Return result if all nodes have been visited
            if next_mask == all_visited:
                return dist + 1
            # If this state is not seen, add it to the queue
            if (neighbor, next_mask) not in seen:
                seen.add((neighbor, next_mask))
                queue.append((neighbor, next_mask, dist + 1))
                
    # Fallback (should not be reached since graph is connected)
    return -1

# Example usage:
# graph = [[1,2,3],[0],[0],[0]]
# print(shortestPathLength(graph))