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.
Flowchart Walkthrough
To decipher the appropriate algorithm for leetcode 847. Shortest Path Visiting All Nodes, let's refer to the algorithm Flowchart. We will navigate through the flowchart step-by-step to determine the suitable method:
Is it a graph?
- Yes: The problem explicitly involves visiting all nodes in a graph.
Is it a tree?
- No: The problem's graph can have cycles and is not necessarily hierarchical.
Is the problem related to directed acyclic graphs (DAGs)?
- No: The graph could potentially include cycles and is not directed acyclic.
Is the problem related to shortest paths?
- Yes: The goal is to find the shortest path that visits all nodes.
Is the graph weighted?
- No: The problem states that each edge has the same weight, implicating an unweighted graph.
Conclusion: Given this problem's focus on an unweighted graph where the goal is to find the shortest path visiting all nodes, the flowchart recommends using Breadth-First Search (BFS) to address this task.
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:
-
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.
-
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 thecollections
module for efficient pops from the front of the list. -
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 as11111
in binary, which is31
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. -
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 acurrent_node
and thevisited_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 returnans
. - If all nodes have not been visited, for each neighbor
j
of thecurrent_node
, calculate the new statenst
by setting the corresponding bit (1 << j
) in thevisited_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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let us consider a small graph represented as an adjacency list for the clarity of our example:
graph = [ [1, 2], // Node 0 is connected to Node 1 and 2 [0, 2, 3], // Node 1 is connected to Node 0, 2, and 3 [0, 1], // Node 2 is connected to Node 0 and 1 [1] // Node 3 is connected to Node 1 ]
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:
- 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 nodes0
,1
,2
, and3
respectively.
- Queue and
ans
is set to0
, marking the starting point of the BFS levels.- 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 is1
and2
. - Update the visited_state to include these neighbors.
- For neighbor
1
,nst
becomes1 | (1 << 1)
which is3
in binary itās011
. - For neighbor
2
,nst
becomes1 | (1 << 2)
which is5
in binary itās101
. - 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), (2, 4), (3, 8), // Remaining initial states (1, 3), (2, 5) // New states after processing Node 0 // More states would be added as we continue the BFS ]
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
1from collections import deque
2
3class Solution:
4 def shortestPathLength(self, graph: List[List[int]]) -> int:
5 num_nodes = len(graph) # Number of nodes in the graph
6 queue = deque()
7 visited = set() # Set to store visited (node, state) tuples
8
9 # Initialize the queue and visited set with all individual nodes and their bitmasks
10 for node in range(num_nodes):
11 state = 1 << node
12 queue.append((node, state))
13 visited.add((node, state))
14
15 # Initialize the number of steps taken to reach all nodes
16 steps = 0
17
18 # Perform a BFS until a path visiting all nodes is found
19 while True:
20 # Iterate over nodes in the current layer
21 for _ in range(len(queue)):
22 current_node, state = queue.popleft()
23 # Check if the current state has all nodes visited
24 if state == (1 << num_nodes) - 1:
25 return steps # Return the number of steps taken so far
26
27 # Explore neighbors of the current node
28 for neighbor in graph[current_node]:
29 new_state = state | (1 << neighbor)
30 # If the new state has not been visited, add it to the queue and set
31 if (neighbor, new_state) not in visited:
32 visited.add((neighbor, new_state))
33 queue.append((neighbor, new_state))
34
35 # After exploring all nodes at the current depth, increment steps
36 steps += 1
37
1class Solution {
2 public int shortestPathLength(int[][] graph) {
3 int numNodes = graph.length; // Number of nodes in the graph
4 Deque<int[]> queue = new ArrayDeque<>(); // Queue for BFS
5 boolean[][] visited = new boolean[numNodes][1 << numNodes]; // Visited states
6
7 // Initialize by adding each node as a starting point in the queue
8 // and marking it visited with its own unique state
9 for (int i = 0; i < numNodes; ++i) {
10 queue.offer(new int[] {i, 1 << i}); // Node index, state as a bit mask
11 visited[i][1 << i] = true;
12 }
13
14 // BFS traversal
15 for (int steps = 0; ; ++steps) { // No terminal condition because the answer is guaranteed to exist
16 for (int size = queue.size(); size > 0; --size) { // Process nodes level by level
17 int[] pair = queue.poll(); // Get pair (node index, state)
18 int node = pair[0], state = pair[1];
19
20 // If state has all nodes visited (all bits set), return the number of steps
21 if (state == (1 << numNodes) - 1) {
22 return steps;
23 }
24
25 // Check the neighbors
26 for (int neighbor : graph[node]) {
27 int newState = state | (1 << neighbor); // Set bit for the neighbor
28 // If this state has not been visited before, mark it visited and add to queue
29 if (!visited[neighbor][newState]) {
30 visited[neighbor][newState] = true;
31 queue.offer(new int[] {neighbor, newState});
32 }
33 }
34 }
35 }
36 }
37}
38
1#include <vector>
2#include <queue>
3#include <cstring>
4
5class Solution {
6public:
7 // Function to find the shortest path that visits all nodes in an undirected graph.
8 int shortestPathLength(vector<vector<int>>& graph) {
9 int nodeCount = graph.size(); // Number of nodes in the graph
10 queue<pair<int, int>> nodesQueue; // Queue to maintain the state
11
12 // Visited array to keep track of visited states: node index and visited nodes bitmask
13 bool visited[nodeCount][1 << nodeCount];
14 memset(visited, false, sizeof(visited)); // Initializing all elements as false
15
16 for (int i = 0; i < nodeCount; ++i) {
17 // Initialize the queue with all nodes as starting points
18 int bitmask = 1 << i; // Binary representation where only the ith bit is set
19 nodesQueue.emplace(i, bitmask);
20 visited[i][bitmask] = true; // Set the initial state as visited
21 }
22
23 // Loop continually, increasing the path length in each iteration
24 for (int pathLength = 0; ; ++pathLength) {
25 int levelSize = nodesQueue.size(); // Number of elements at the current level of BFS
26 while (levelSize--) { // Loop over all nodes in the current BFS level
27 auto [currentNode, stateBitmask] = nodesQueue.front(); // Fetch the front element
28 nodesQueue.pop(); // Remove the element from the queue
29
30 // If the state bitmask represents all nodes visited, return the current path length
31 if (stateBitmask == (1 << nodeCount) - 1) {
32 return pathLength;
33 }
34
35 // Explore adjacent nodes
36 for (int nextNode : graph[currentNode]) {
37 int nextStateBitmask = stateBitmask | (1 << nextNode); // Update the visited mask
38 if (!visited[nextNode][nextStateBitmask]) { // If this state has not been visited
39 visited[nextNode][nextStateBitmask] = true; // Mark it as visited
40 nodesQueue.emplace(nextNode, nextStateBitmask); // Add to the queue
41 }
42 }
43 }
44 }
45 }
46};
47
1function shortestPathLength(graph: number[][]): number {
2 // The 'n' represents the total number of nodes in the graph.
3 const nodeCount = graph.length;
4
5 // The queue to perform BFS. Elements are pairs: [node, state].
6 const queue: number[][] = [];
7
8 // Visited states represented by node index and state as a bitmask.
9 const visited: boolean[][] = Array.from({ length: nodeCount }, () =>
10 new Array(1 << nodeCount).fill(false));
11
12 // Initialize queue and visited with the starting nodes and their respective bitmasks.
13 for (let i = 0; i < nodeCount; i++) {
14 const startState = 1 << i; // Initial state for node i (only node i has been visited).
15 queue.push([i, startState]);
16 visited[i][startState] = true;
17 }
18
19 // BFS to find the shortest path length.
20 for (let steps = 0; ; steps++) {
21 // Iterate through the current level of the queue.
22 for (let size = queue.length; size > 0; size--) {
23 const [currentNode, state] = queue.shift()!; // Get next element from the queue.
24
25 // If all nodes have been visited, return the number of steps taken.
26 if (state === (1 << nodeCount) - 1) {
27 return steps;
28 }
29
30 // Check all neighbors of the current node.
31 for (const nextNode of graph[currentNode]) {
32 const nextState = state | (1 << nextNode); // Mark nextNode as visited in the state.
33
34 // If the state is not yet visited for the nextNode, mark it and enqueue.
35 if (!visited[nextNode][nextState]) {
36 visited[nextNode][nextState] = true;
37 queue.push([nextNode, nextState]);
38 }
39 }
40 }
41 }
42}
43
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 areN
nodes and2^N
possible states, the set size can go up toN * 2^N
. - A queue
q
is used to perform BFS, this queue will also store at mostN * 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.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Want a Structured Path to Master System Design Too? Donāt Miss This!