847. Shortest Path Visiting All Nodes

At a Glance

Topic: advanced-graphs
Pattern: BFS on (visitedMask, lastNode) state graph — Traveling Salesman / Held–Karp bitmask
Difficulty: Hard
Companies: Google, Amazon, Meta, Microsoft, Citadel
Frequency: Medium
LeetCode: 847

Problem (one-liner)

Undirected connected graph on n nodes 0..n-1. Return length of shortest path (walk; nodes may repeat) that visits every node at least once and ends anywhere.

Recognition Cues

Visit all nodes — bitmask over n <= 12
Shortest walk length — BFS in expanded graph is simpler than DP recurrence for path length
State must remember last vertex to extend walk correctly

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

DP over subsets — O(n^2 * 2^n) transition over neighbors — works.
Multi-source BFS on (mask, node) — layers equal walk length — same complexity, often clearer — optimal.

Optimal Solution

Go

func shortestPathLength(graph [][]int) int {
	nodeCount := len(graph)
	if nodeCount == 0 {
		return 0
	}
	allVisited := (1 << nodeCount) - 1
	type state struct {
		mask int
		node int
	}
	distance := map[state]int{}
	queue := []state{}
	for start := 0; start < nodeCount; start++ {
		begin := state{mask: 1 << start, node: start}
		distance[begin] = 0
		queue = append(queue, begin)
	}
	head := 0
	for head < len(queue) {
		current := queue[head]
		head++
		if current.mask == allVisited {
			return distance[current]
		}
		for _, neighbor := range graph[current.node] {
			nextMask := current.mask | (1 << neighbor)
			next := state{mask: nextMask, node: neighbor}
			if _, seen := distance[next]; seen {
				continue
			}
			distance[next] = distance[current] + 1
			queue = append(queue, next)
		}
	}
	return -1
}

JavaScript

function shortestPathLength(graph) {
  const nodeCount = graph.length;
  if (nodeCount === 0) {
    return 0;
  }
  const allVisited = (1 << nodeCount) - 1;
  const distance = new Map();
  const queue = [];
  for (let start = 0; start < nodeCount; start += 1) {
    const key = `${1 << start},${start}`;
    distance.set(key, 0);
    queue.push({ mask: 1 << start, node: start });
  }
  let head = 0;
  while (head < queue.length) {
    const current = queue[head];
    head += 1;
    const currentKey = `${current.mask},${current.node}`;
    if (current.mask === allVisited) {
      return distance.get(currentKey);
    }
    for (const neighbor of graph[current.node]) {
      const nextMask = current.mask | (1 << neighbor);
      const nextKey = `${nextMask},${neighbor}`;
      if (distance.has(nextKey)) {
        continue;
      }
      distance.set(nextKey, distance.get(currentKey) + 1);
      queue.push({ mask: nextMask, node: neighbor });
    }
  }
  return -1;
}

Multi-source BFS seeds every singleton mask {start}. Transitions append edges in original graph, OR-ing visited bits. First time mask is all-ones, path length is minimal because BFS explores by increasing steps.

Invariant: distance[(mask,node)] is shortest walk length ending at node having visited exactly the set in mask (superset semantics via OR).

Edge Cases

n == 1 — answer 0
Clique — walk visits each once; BFS still fine
Sparse graph — revisiting helps shortcut — state graph handles repeats

Pitfalls

Forgetting multi-source start — single start may be suboptimal end position
Using visited array without lastNode — loses correctness

Variants

Return one optimal tour — backtrack from final states using parent pointers.
Weighted edges — Dijkstra on (mask, node) states.
Closed tour (return to start) — add return edge cost in the objective.

Mind-Map Tags

#bfs #bitmask #tsp-walk #multi-source #state-space-shortest-path