Shortest Path Visiting All Nodes — Editorial

Opening the reading…

Intuitionthe path is shortest in a larger state graph

A position in this problem is not determined only by the node where you currently stand. Reaching node 2 after visiting only nodes 0 and 2 is different from reaching node 2 after visiting every node except 7. The next moves may look identical, but the second situation is much closer to the goal. Therefore, a useful state must contain the current node and the complete set of visited nodes.

Encode the visited set as a bitmask: bit i is 1 exactly when node i has been visited. From state (u, mask), moving across an edge to v creates (v, mask with bit v turned on). Every edge traversal costs one, so BFS over these states finds the first state whose mask contains every node. Starting BFS from all nodes at once is necessary because the path may begin anywhere.

The visited set changes the meaning of being at the same node.

ApproachBFS on node-mask states

Let n be the number of nodes and let full = (1 << n) - 1, whose n low bits are all 1, because this gives one direct value for the condition that every node has been visited.

Create dist[u][mask] and set every entry to -1, because the same node must be allowed to appear again when the visited set is different.

Insert every starting state (i, 1 << i) into the queue with distance zero, because no starting node is privileged and omitting one could miss the shortest path.

Remove a state (u, mask) from the queue and try every neighbor v of u, because one graph edge corresponds to exactly one BFS transition.

Build nextMask = mask | (1 << v), because visiting v should preserve all earlier visited nodes while adding v if it was not already present.

If dist[v][nextMask] is still -1, record its distance and enqueue it, because BFS reaches states in nondecreasing path length and the first visit is therefore shortest.

Return the distance as soon as a dequeued state has mask == full, because BFS guarantees that no later state can represent a shorter path.

Complexitythe exponential part comes from subsets, not from path enumeration

MEASURE	BOUND	WHY
Time	O((n + m) x 2^n)	There are at most n x 2^n states, and each state scans the adjacency list of its current node. Summed over all masks, each node's adjacency entries are scanned 2^n times, giving O(m x 2^n) for an undirected adjacency representation, while initializing and managing the state table contributes O(n x 2^n).
Space	O(n x 2^n)	The distance table has one entry for every node-mask pair, and the queue can hold that many discovered states in the worst case. The input adjacency lists and the returned integer are excluded from extra working space; this bound is reached when many distinct masks are reachable.

Here n is the number of nodes and m is the number of undirected edges. There are n x 2^n possible node-mask states.

Annotated solutionC++ · multi-source BFS over compressed visited sets

CPPMulti-source BFS where each state stores the current node and its visited-node bitmask.

#include <algorithm>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = static_cast<int>(graph.size());
        if (n <= 1) {
            return 0;
        }

        int full = (1 << n) - 1;
        vector<vector<int>> dist(n, vector<int>(1 << n, -1));
        queue<pair<int, int>> q;

        for (int i = 0; i < n; ++i) {
            int startMask = 1 << i;
            dist[i][startMask] = 0;
            q.push({i, startMask});
        }

        while (!q.empty()) {
            pair<int, int> state = q.front();
            q.pop();

            int u = state.first;
            int mask = state.second;

            if (mask == full) {
                return dist[u][mask];
            }

            for (int v : graph[u]) {
                int nextMask = mask | (1 << v);
                if (dist[v][nextMask] == -1) {
                    dist[v][nextMask] = dist[u][mask] + 1;
                    q.push({v, nextMask});
                }
            }
        }

        return -1;
    }
};

The crucial initialization puts one state for every possible start into the same BFS layer. This is equivalent to adding a fictional source connected to every graph node by zero-cost edges, so the first complete-mask state found is the best path regardless of where that path begins.

The distance table is also the visited structure, but its key is the pair of node and mask. Revisiting a graph node is often useful because the new arrival may have collected a different node in the meantime. Marking only the node would discard those possibilities and turn a valid shortest-path search into an incomplete one.

The DP alternative uses the same state spacea different arrangement, not an asymptotic improvement

You can view the same problem as shortest distance in a product graph whose vertices are pairs (node, mask). A dynamic-programming implementation may relax transitions repeatedly, or use a priority queue to process states by distance. That arrangement is usually less direct than BFS because every transition has unit cost. It buys a more general shortest-path viewpoint, but it does not improve the O((n + m) x 2^n) time or O(n x 2^n) space bounds.