# 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:

```python
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:

| Rule | Meaning |
|---|---|
| Start | We may start at any node |
| End | We may stop at any node |
| Revisiting nodes | Allowed |
| Reusing edges | Allowed |
| Goal | Visit every node at least once |

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

| Item | Meaning |
|---|---|
| Input | An adjacency list `graph` |
| Output | Minimum number of edges needed to visit all nodes |
| Graph type | Undirected and connected |
| Node labels | `0` to `n - 1` |
| Constraint idea | `n` is small enough for bitmask state search |

Function shape:

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

## Examples

Example 1:

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

This is a star-shaped graph:

```python
    1
    |
2 - 0 - 3
```

One shortest path is:

```python
1 -> 0 -> 2 -> 0 -> 3
```

This path visits all nodes and has length `4`.

So the answer is:

```python
4
```

Example 2:

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

One shortest path is:

```python
0 -> 1 -> 4 -> 2 -> 3
```

It visits all nodes and has length `4`.

So the answer is:

```python
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:

```python
(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:

| Mask | Meaning |
|---|---|
| `0001` | Visited node `0` |
| `0011` | Visited nodes `0` and `1` |
| `1011` | Visited nodes `0`, `1`, and `3` |
| `1111` | Visited all nodes |

The target mask is:

```python
(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:

```python
(node, 1 << node)
```

for every node.

This means:

| Start state | Meaning |
|---|---|
| `(0, 0001)` | Start at node `0` |
| `(1, 0010)` | Start at node `1` |
| `(2, 0100)` | Start at node `2` |

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:
   ```python id="byuhmz"
   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:
         ```python id="4x527r"
         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:

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

There are `4` nodes, so:

```python
target = 1111
```

Initial BFS states:

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

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

```python
(0, 0011)
```

This path is:

```python
1 -> 0
```

From there, move to node `2`:

```python
(2, 0111)
```

Path:

```python
1 -> 0 -> 2
```

Then move back to node `0`:

```python
(0, 0111)
```

Path:

```python
1 -> 0 -> 2 -> 0
```

Then move to node `3`:

```python
(3, 1111)
```

Now all nodes have been visited.

The path length is `4`.

So the answer is:

```python
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:

```python
n = len(graph)
```

There are:

```python
n * 2^n
```

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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n * 2^n + E * 2^n)` | Each state-edge transition may be processed |
| Space | `O(n * 2^n)` | Store visited states and BFS queue |

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

```python
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:

```python
target = (1 << n) - 1
```

For example, if `n = 4`:

```python
target = 1111
```

We initialize BFS from every node:

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

The queue stores:

```python
(current node, visited mask, distance)
```

For each neighbor:

```python
next_mask = mask | (1 << neighbor)
```

sets the neighbor's bit to mark it visited.

If all bits are set:

```python
if next_mask == target:
    return dist + 1
```

we have visited every node.

The `visited` set stores states, not just nodes:

```python
state = (neighbor, next_mask)
```

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

## Testing

```python
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:

| Test | Why |
|---|---|
| Star graph | Confirms revisiting center is allowed |
| Standard example | Confirms shortest walk can stop anywhere |
| Single node | Confirms length `0` |
| Two nodes | Confirms one edge is enough |
| Path graph | Confirms straight traversal |
| Complete triangle | Confirms dense graph shortest path |