LeetCode 847 - Shortest Path Visiting All Nodes

The problem gives us an undirected and connected graph with n nodes labeled from 0 to n - 1. The graph is represented as an adjacency list, where graph[i] contains all nodes directly connected to node i.

leetcodeharddynamic-programmingbit-manipulationbreadth-first-searchgraph-theorybitmask

LeetCode Problem 847

Difficulty: 🔴 Hard
Topics: Dynamic Programming, Bit Manipulation, Breadth-First Search, Graph Theory, Bitmask

Solution

Problem Understanding

The problem gives us an undirected and connected graph with n nodes labeled from 0 to n - 1. The graph is represented as an adjacency list, where graph[i] contains all nodes directly connected to node i.

We must compute the length of the shortest path that visits every node at least once. The path may begin at any node and may end at any node. We are also allowed to revisit nodes and reuse edges multiple times.

The key detail is that we are not asked to find a Hamiltonian path. A Hamiltonian path requires visiting every node exactly once, which is an NP-hard problem. Here, revisiting nodes is allowed, which makes the problem solvable using state-based graph traversal techniques.

The output is the minimum number of edges traversed to visit all nodes.

For example, in the first sample:

0 connected to 1, 2, 3

One valid shortest traversal is:

1 -> 0 -> 2 -> 0 -> 3

This path uses 4 edges, so the answer is 4.

The constraints are especially important:

  • 1 <= n <= 12
  • The graph is connected
  • The graph is undirected

Since n is at most 12, the total number of subsets of nodes is:

2^12 = 4096

This is small enough for bitmask-based dynamic programming or breadth-first search over states.

The important edge cases include:

  • A graph with only one node. Since we already start on that node, the answer is 0.
  • Sparse graphs where revisiting nodes is necessary.
  • Dense graphs where many traversal choices exist.
  • Star-shaped graphs where the center node must be revisited repeatedly.
  • Cyclic graphs where multiple shortest traversals may exist.

The problem guarantees that the graph is connected, so we never need to handle unreachable nodes.

Approaches

Brute Force Approach

A brute-force solution would try all possible paths starting from every node and keep track of which nodes have been visited.

At every step, we could recursively move to neighboring nodes and continue until all nodes have been visited. We would then record the minimum path length among all valid traversals.

This approach is correct because it exhaustively explores every possible traversal sequence. Eventually, it will discover the shortest one.

However, the number of possible traversal sequences grows exponentially. Since revisiting nodes is allowed, the search space becomes enormous. Even with pruning, the number of states explodes very quickly.

This approach is far too slow for n = 12.

Optimal Approach, Multi-Source BFS with Bitmasking

The key insight is that the important information is not just the current node, but also which nodes have already been visited.

This means the true state is:

(current_node, visited_nodes_mask)

We can represent visited nodes using a bitmask:

  • Bit i is 1 if node i has been visited.
  • Bit i is 0 otherwise.

For example:

mask = 1011

means nodes 0, 1, and 3 have been visited.

We then perform breadth-first search over these states.

Since BFS explores states level by level, the first time we reach a state where all nodes are visited, we are guaranteed to have found the shortest path length.

Another important optimization is multi-source BFS.

Instead of trying every starting node separately, we initialize the BFS queue with all nodes simultaneously:

(node=i, mask=(1 << i))

This means BFS explores all possible starting positions in parallel.

The total number of states is:

n * 2^n

which is manageable for n <= 12.

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Tries all traversal possibilities recursively
Optimal O(n × 2^n) O(n × 2^n) BFS over (node, mask) states

Algorithm Walkthrough

  1. Compute the final target mask.

We want a bitmask where every node has been visited.

If there are n nodes:

target_mask = (1 << n) - 1

For example, if n = 4:

target_mask = 1111
  1. Initialize the BFS queue with every node.

Since we may start from any node, we begin BFS from all nodes simultaneously.

For each node i:

state = (i, 1 << i)

This means:

  • We are currently at node i
  • Only node i has been visited
  1. Maintain a visited-state structure.

We must avoid revisiting the same state repeatedly.

A state is uniquely identified by:

(current_node, visited_mask)

Even if we revisit the same node, the state may still be different if the visited set changes. 4. Perform BFS level by level.

Each BFS level represents one additional edge traversal.

For every state:

  • Extract (node, mask)
  • Visit all neighbors
  • Create a new mask:
new_mask = mask | (1 << neighbor)

This marks the neighbor as visited. 5. Check whether all nodes have been visited.

If:

new_mask == target_mask

then we have visited every node.

Since BFS guarantees shortest distance first, we immediately return the current distance plus one. 6. Continue until the answer is found.

Because the graph is connected, BFS is guaranteed to eventually reach the full mask state.

Why it works

BFS always explores paths in increasing order of length. Each state fully captures both our current position and which nodes have already been visited. Therefore, the first time BFS reaches a state where all nodes are visited, that path must be the shortest possible traversal that visits every node.

Python Solution

from collections import deque
from typing import List

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        n = len(graph)

        if n == 1:
            return 0

        target_mask = (1 << n) - 1

        queue = deque()
        visited = set()

        for node in range(n):
            mask = 1 << node
            queue.append((node, mask, 0))
            visited.add((node, mask))

        while queue:
            current_node, mask, distance = queue.popleft()

            for neighbor in graph[current_node]:
                new_mask = mask | (1 << neighbor)

                if new_mask == target_mask:
                    return distance + 1

                state = (neighbor, new_mask)

                if state not in visited:
                    visited.add(state)
                    queue.append((neighbor, new_mask, distance + 1))

        return -1

The implementation begins by handling the simplest edge case. If the graph contains only one node, no traversal is required, so the answer is immediately 0.

Next, we compute the target bitmask where every bit is set to 1. This represents the state where all nodes have been visited.

The queue stores BFS states in the form:

(current_node, visited_mask, distance)

We initialize the queue with every node because the traversal may start anywhere. This is what makes the algorithm a multi-source BFS.

The visited set prevents redundant work. Revisiting the same node with the same mask provides no benefit because BFS already reached that state with the shortest possible distance.

Inside the BFS loop, we process neighbors and update the visited mask using bitwise OR:

new_mask = mask | (1 << neighbor)

If the updated mask equals the target mask, then every node has been visited. Since BFS explores shortest paths first, we return immediately.

Otherwise, we enqueue the new state if it has not already been processed.

Go Solution

package main

import "container/list"

func shortestPathLength(graph [][]int) int {
	n := len(graph)

	if n == 1 {
		return 0
	}

	targetMask := (1 << n) - 1

	type State struct {
		node     int
		mask     int
		distance int
	}

	queue := list.New()

	visited := make(map[[2]int]bool)

	for i := 0; i < n; i++ {
		mask := 1 << i

		queue.PushBack(State{
			node:     i,
			mask:     mask,
			distance: 0,
		})

		visited[[2]int{i, mask}] = true
	}

	for queue.Len() > 0 {
		front := queue.Front()
		queue.Remove(front)

		current := front.Value.(State)

		for _, neighbor := range graph[current.node] {
			newMask := current.mask | (1 << neighbor)

			if newMask == targetMask {
				return current.distance + 1
			}

			stateKey := [2]int{neighbor, newMask}

			if !visited[stateKey] {
				visited[stateKey] = true

				queue.PushBack(State{
					node:     neighbor,
					mask:     newMask,
					distance: current.distance + 1,
				})
			}
		}
	}

	return -1
}

The Go implementation follows the same algorithmic structure as the Python solution.

Since Go does not provide a built-in deque, we use container/list to implement the BFS queue.

The visited-state structure uses a map with a fixed-size array key:

map[[2]int]bool

where the array stores:

[node, mask]

Go integers are sufficient because the maximum bitmask size is only 2^12.

Worked Examples

Example 1

graph = [[1,2,3],[0],[0],[0]]

There are 4 nodes.

The target mask is:

1111

Initial queue:

Node Mask Binary Mask Distance
0 1 0001 0
1 2 0010 0
2 4 0100 0
3 8 1000 0

Process (1, 0010):

Neighbor is 0.

New mask:

0010 | 0001 = 0011

Queue now contains:

Node Mask Binary Mask Distance
0 3 0011 1

From (0, 0011):

Visit node 2.

0011 | 0100 = 0111

Now we have visited nodes 0,1,2.

Distance becomes 2.

From (0, 0111):

Visit node 3.

0111 | 1000 = 1111

All nodes are visited.

Answer:

4

Example 2

graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]

There are 5 nodes.

Target mask:

11111

One shortest traversal discovered by BFS is:

0 -> 1 -> 4 -> 2 -> 3

Mask progression:

Current Node Mask
0 00001
1 00011
4 10011
2 10111
3 11111

All nodes become visited after 4 edges.

Answer:

4

Complexity Analysis

Measure Complexity Explanation
Time O(n × 2^n) Each (node, mask) state is processed at most once
Space O(n × 2^n) Queue and visited set store state combinations

The graph has at most:

n * 2^n

distinct states because:

  • There are n possible current nodes
  • There are 2^n possible visited masks

Each state is processed once during BFS. For each state, we iterate through neighboring edges. Since n <= 12, this complexity is efficient enough for the problem constraints.

Test Cases

from typing import List

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        from collections import deque

        n = len(graph)

        if n == 1:
            return 0

        target_mask = (1 << n) - 1

        queue = deque()
        visited = set()

        for node in range(n):
            mask = 1 << node
            queue.append((node, mask, 0))
            visited.add((node, mask))

        while queue:
            node, mask, dist = queue.popleft()

            for neighbor in graph[node]:
                new_mask = mask | (1 << neighbor)

                if new_mask == target_mask:
                    return dist + 1

                state = (neighbor, new_mask)

                if state not in visited:
                    visited.add(state)
                    queue.append((neighbor, new_mask, dist + 1))

        return -1

solution = Solution()

assert solution.shortestPathLength([[1,2,3],[0],[0],[0]]) == 4
# Star graph from problem statement

assert solution.shortestPathLength([[1],[0,2,4],[1,3,4],[2],[1,2]]) == 4
# Graph with cycles from problem statement

assert solution.shortestPathLength([[]]) == 0
# Single-node graph

assert solution.shortestPathLength([[1],[0]]) == 1
# Two connected nodes

assert solution.shortestPathLength([[1,2],[0,2],[0,1]]) == 2
# Triangle graph

assert solution.shortestPathLength([[1],[0,2],[1,3],[2]]) == 3
# Linear chain

assert solution.shortestPathLength([
    [1,2,3],
    [0],
    [0],
    [0,4],
    [3]
]) == 5
# Requires revisiting central nodes

assert solution.shortestPathLength([
    [1,5],
    [0,2],
    [1,3],
    [2,4],
    [3,5],
    [4,0]
]) == 5
# Cycle graph
Test Why
[[1,2,3],[0],[0],[0]] Validates star-shaped graph traversal
[[1],[0,2,4],[1,3,4],[2],[1,2]] Validates cyclic graph behavior
[[]] Validates single-node edge case
[[1],[0]] Smallest connected graph
[[1,2],[0,2],[0,1]] Dense triangle graph
[[1],[0,2],[1,3],[2]] Linear chain traversal
Mixed star-chain graph Ensures revisiting nodes works correctly
Cycle graph Ensures BFS handles loops efficiently

Edge Cases

Single Node Graph

If the graph contains only one node, we have already visited every node before making any moves. A buggy implementation might still run BFS unnecessarily or return an incorrect positive distance.

The implementation handles this immediately with:

if n == 1:
    return 0

Revisiting Nodes is Necessary

Some graphs require revisiting previously visited nodes to reach remaining unvisited nodes. Star graphs are a classic example.

For instance:

    1
    |
2 - 0 - 3

To visit every node, we must repeatedly return to node 0.

A solution incorrectly assuming each node can only be visited once would fail. Our state representation only tracks whether a node has been visited at least once, not whether it can be revisited.

Multiple Ways to Reach the Same Node

It is possible to arrive at the same node with different visited-node sets.

For example:

(node=2, mask=0111)
(node=2, mask=1011)

These are completely different states because the set of visited nodes differs.

A buggy implementation that only tracks visited nodes by current vertex would incorrectly prune valid paths. Our implementation stores the full (node, mask) pair, ensuring correctness.

Dense Graphs with Many Cycles

Dense graphs can generate many repeated traversal opportunities.

Without proper state deduplication, BFS would repeatedly process identical states and become extremely slow.

The visited set guarantees each unique (node, mask) state is processed only once, preventing exponential duplication.