847. Shortest Path Visiting All Nodes

Problem Description

In this LeetCode problem, we are given an undirected, connected graph with n nodes, where nodes are labeled from 0 to n - 1. The graph is represented as an adjacency list: graph[i] contains all the nodes connected to the node i by an edge. Our goal is to determine the shortest path length that visits every node in the graph. We are allowed to start and end at any node, revisit nodes, and traverse any edge multiple times if needed.

The key challenge is to visit all nodes in the most efficient way possible, keeping the path as short as we can manage. It is important to note that the problem isn't asking for the shortest path between two particular nodes, but rather a path that covers all nodes.

Intuition

To solve this problem, we'll use Breadth-First Search (BFS) algorithm paired with state compression to keep track of the nodes visited. The intuition here is that since all edges are equally weighted, BFS is a natural choice to find the shortest path in undirected graphs.

State compression is used here to efficiently represent the set of nodes visited at any point in time. This is crucial because revisiting nodes is allowed, hence the state of our search isn't just the current node, but also the collection of nodes that have been visited so far. By using a bitmask to represent visited nodes (where the i-th bit corresponds to whether the i-th node has been visited), we can easily update and check which nodes have been seen as we process the BFS queue.

For each node, we start a BFS traversal, where each element in the BFS queue is a pair (current_node, visited_state). We define the initial state as 1 << i, which means only the node i is visited. If the visited state ever becomes (1 << n) - 1, it indicates all nodes have been visited, and we have our solution: the length of the path taken to reach this state.

The BFS ensures we find the shortest such path, and the visited set (vis) prevents us from processing the same state (node + visited combination) more than once, which is essential to avoid infinite loops and reduce computation.

Learn more about Breadth-First Search, Graph, Dynamic Programming and Bitmask patterns.

Solution Approach

The solution leverages the BFS algorithm and bitmasking for state tracking to efficiently determine the shortest path that visits every node in the graph. The approach can be broken down into key components that work synchronously to find the solution:

1. Breadth-First Search (BFS): BFS algorithm is a perfect fit to find the shortest path in a graph with edges of equal weight. It starts traversing from a node and explores all its neighbors before moving onto the neighbors of those neighbors, thus ensuring that the shortest paths to all nodes are identified.

2. Queue: The algorithm uses a queue data structure to process nodes in FIFO (first-in-first-out) order, which is the essence of BFS. In Python, this is implemented using the deque data structure from the collections module for efficient pops from the front of the list.

3. State Compression with Bitmasking: To track the nodes that have been visited during the traversal without actually storing all the nodes themselves, state compression through bitmasking is used. For instance, if five nodes have been visited in a graph with n = 5 nodes, the visited state can be represented as 11111 in binary, which is 31 in decimal. This approach drastically reduces the memory footprint and makes the check for the condition of all nodes being visited (st == (1 << n) - 1) straightforward.

4. Visited Set: A set named vis is used to keep track of all the (node, state) pairs that have been visited. This is to avoid repeating searches that have already been done and to ensure we do not go into cycles, which can be a common issue in graph problems.

The implementation steps are as follows:

• Initialize the queue and visited set, and populate them with the first step of the BFS, which includes every node visited on its own first ((i, 1 << i)).
• Set ans to zero, which will keep track of the number of steps from the start.
• Begin the while loop, which will run until we break out of it when the solution is found.
• Iterate over the queue. Remove (popleft) the front of the queue to process the current state. Each state contains a current_node and the visited_state.
• Check if the visited state signifies that all nodes have been visited by comparing it to (1 << n) - 1 (which represents a state where all nodes have been visited). If so, this is the shortest path, and we return ans.
• If all nodes have not been visited, for each neighbor j of the current_node, calculate the new state nst by setting the corresponding bit (1 << j) in the visited_state.
• If this new state has not been visited (if (j, nst) not in vis), add it to the visited set and queue.
• If the inner loop completes without returning, increment ans to indicate that another level of BFS is completed.

Example Walkthrough

Let us consider a small graph represented as an adjacency list for the clarity of our example:

1graph = [
2  [1, 2],    // Node 0 is connected to Node 1 and 2
3  [0, 2, 3], // Node 1 is connected to Node 0, 2, and 3
4  [0, 1],    // Node 2 is connected to Node 0 and 1
5  [1]        // Node 3 is connected to Node 1
6]

This is an undirected graph with n = 4 nodes. The goal is to find the shortest path that visits all nodes.

Let's walk through the steps of the BFS algorithm and state compression starting from Node 0:

1. Initialize the BFS queue with our starting nodes and initial state and the visited set vis.
   • Queue and vis will have the following entries: [(0, 1), (1, 2), (2, 4), (3, 8)] where each pair has the format (current_node, visited_state).
   • 1, 2, 4, 8 are the bitmask states for visiting nodes 0, 1, 2, and 3 respectively.
2. ans is set to 0, marking the starting point of the BFS levels.
3. We start our while loop, processing the states in our queue one by one.

Processing current_node = 0, visited_state = 1:

• We check each neighbor of node 0, which is 1 and 2.
• Update the visited_state to include these neighbors.
• For neighbor 1, nst becomes 1 | (1 << 1) which is 3 in binary it’s 011.
• For neighbor 2, nst becomes 1 | (1 << 2) which is 5 in binary it’s 101.
• Since these new states have not been visited, we add them to vis and queue: [(1, 3), (2, 5)].

After processing all initial states and their neighbors, we increment ans to 1, which reflects moving to a new level in our BFS search. The queue and vis have been updated with the new states.

Queue now looks like:

1[
2  (1, 2), (2, 4), (3, 8), // Remaining initial states
3  (1, 3), (2, 5)          // New states after processing Node 0
4  // More states would be added as we continue the BFS
5]

This process continues, applying BFS. Each node visits its neighbors, creates new states, adds them to the queue if not already visited, and checks if the visited state equates to (1 << n) - 1. If at any point the visited state becomes 1111 (15 in decimal), this means all nodes have been visited, and the value of ans at this point will give us our shortest path length.

Upon finding this condition, the BFS stops, and we return ans as the length of the shortest path to visit all nodes.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the provided code can be considered as O(N * 2^N) where N is the number of nodes in the graph. Here's the breakdown:

• The algorithm uses Breadth-First Search (BFS) to traverse through every possible state of visited nodes.
• There are 2^N possible states since each node can either be visited or not, marked by bitmasks.
• For each state, we go through all the N nodes and perform constant-time operations (a bitwise OR to update the state and some checks).
• The outer loop iterates until the queue is empty, and since we enqueue each state at most once, it iterates N * 2^N times across all layers of BFS.

Space Complexity

The space complexity is O(N * 2^N), which arises from the following:

• A vis set is maintained to keep track of visited states to ensure that each state is processed exactly once. Since there are N nodes and 2^N possible states, the set size can go up to N * 2^N.
• A queue q is used to perform BFS, this queue will also store at most N * 2^N elements, which are pairs of current node and the state of visited nodes up to that point.

Learn more about how to find time and space complexity quickly using problem constraints.