LeetCode 847: Shortest Path Visiting All Nodes

Problem Restatement

We are given an undirected connected graph with n nodes labeled from 0 to n - 1.

The graph is given as an adjacency list:

graph[i]

contains all nodes directly connected to node i.

We need to return the length of the shortest path that visits every node at least once.

Important details:

The official statement says to return the length of the shortest path that visits every node, with arbitrary start and stop nodes, and allows revisiting nodes and reusing edges.

Input and Output

Function shape:

class Solution:
    def shortestPathLength(self, graph: list[list[int]]) -> int:
        ...

Examples

Example 1:

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

This is a star-shaped graph:

    1
    |
2 - 0 - 3

One shortest path is:

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

This path visits all nodes and has length 4.

So the answer is:

4

Example 2:

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

One shortest path is:

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

It visits all nodes and has length 4.

So the answer is:

4

First Thought: Try DFS From Every Node

A direct approach is to try all possible walks through the graph until all nodes are visited.

But a walk may revisit nodes and edges. This creates many possibilities.

For example, from a node, we can move to any neighbor, then any neighbor again, and so on.

A plain DFS can easily revisit the same situation many times.

We need a way to remember not only where we are, but also which nodes we have already visited.

Key Insight

The current node alone is not enough state.

For example, reaching node 3 after visiting {0, 1, 3} is different from reaching node 3 after visiting {2, 3}.

The future options may look similar, but the remaining nodes are different.

So the correct state is:

(current_node, visited_mask)

The visited_mask is a bitmask.

If node i has been visited, bit i is 1.

For example, with 4 nodes:

The target mask is:

(1 << n) - 1

This is the mask where all n bits are set.

Since every edge has equal cost 1, BFS over these states gives the shortest path.

Why Multi-Source BFS

We may start at any node.

Instead of running BFS once from each possible starting node, we start BFS from all nodes at the same time.

Initial states are:

(node, 1 << node)

for every node.

This means:

The first time BFS reaches a state whose mask has all nodes visited, that distance is the shortest possible path length from any starting node.

Algorithm

1. Let n = len(graph).
2. If n == 1, return 0.
3. Compute:

   target = (1 << n) - 1
4. Create a queue.
5. Add every starting state (node, 1 << node, 0) to the queue.
6. Mark each starting state as visited.
7. While the queue is not empty:
   1. Pop (node, mask, dist).
   2. For each neighbor:
      1. Compute:

         next_mask = mask | (1 << neighbor)
      2. If next_mask == target, return dist + 1.
      3. If (neighbor, next_mask) was not visited, add it to the queue.

Walkthrough

Use:

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

There are 4 nodes, so:

target = 1111

Initial BFS states:

(0, 0001)
(1, 0010)
(2, 0100)
(3, 1000)

From (1, 0010), move to node 0:

(0, 0011)

This path is:

1 -> 0

From there, move to node 2:

(2, 0111)

Path:

1 -> 0 -> 2

Then move back to node 0:

(0, 0111)

Path:

1 -> 0 -> 2 -> 0

Then move to node 3:

(3, 1111)

Now all nodes have been visited.

The path length is 4.

So the answer is:

4

Correctness

Each BFS state records exactly two pieces of information: the current node and the set of nodes already visited.

When the algorithm moves from node to neighbor, it follows one real graph edge. The new visited mask correctly adds neighbor by setting its bit.

Therefore, every state reached by the BFS corresponds to a real walk in the graph.

Conversely, every valid walk through the graph corresponds to a sequence of these states, because after each step we know the current node and the set of visited nodes.

BFS explores states in increasing order of path length because every edge transition costs exactly 1.

The initial queue contains all possible starting nodes with distance 0, so the BFS considers every allowed start.

The first time the BFS reaches a state whose mask equals target, it has found the shortest walk that visits every node. If a shorter such walk existed, BFS would have reached a full-mask state earlier.

Therefore, the returned distance is the shortest path length that visits all nodes.

Complexity

Let:

n = len(graph)

There are:

n * 2^n

possible states, because there are n possible current nodes and 2^n possible visited masks.

For dense graphs, E can be O(n^2), so time can be written as O(n^2 * 2^n).

For this problem, n is small, which makes bitmask BFS practical.

Implementation

from collections import deque

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

        if n == 1:
            return 0

        target = (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]:
                next_mask = mask | (1 << neighbor)

                if next_mask == target:
                    return dist + 1

                state = (neighbor, next_mask)

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

        return 0

Code Explanation

The target mask has all nodes visited:

target = (1 << n) - 1

For example, if n = 4:

target = 1111

We initialize BFS from every node:

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

The queue stores:

(current node, visited mask, distance)

For each neighbor:

next_mask = mask | (1 << neighbor)

sets the neighbor’s bit to mark it visited.

If all bits are set:

if next_mask == target:
    return dist + 1

we have visited every node.

The visited set stores states, not just nodes:

state = (neighbor, next_mask)

This matters because reaching the same node with different visited sets are different situations.

Testing

def run_tests():
    s = Solution()

    assert s.shortestPathLength([[1, 2, 3], [0], [0], [0]]) == 4

    assert s.shortestPathLength([
        [1],
        [0, 2, 4],
        [1, 3, 4],
        [2],
        [1, 2],
    ]) == 4

    assert s.shortestPathLength([[]]) == 0

    assert s.shortestPathLength([[1], [0]]) == 1

    assert s.shortestPathLength([[1], [0, 2], [1, 3], [2]]) == 3

    assert s.shortestPathLength([[1, 2], [0, 2], [0, 1]]) == 2

    print("all tests passed")

run_tests()

Test meaning: