Shortest Path Visiting All Nodes - Video Solutions

Problem Overview: You are given an undirected connected graph and need the minimum number of steps required to visit every node at least once. You can start from any node and revisit nodes or edges if needed, but the goal is to minimize the total path length.

Approach 1: Brute Force DFS / Backtracking (Exponential Time)

A naive strategy tries every possible path using depth‑first search and keeps track of which nodes have been visited. Each recursive call explores all neighbors while maintaining a visited set. Because nodes can be revisited and the order of visiting matters, the number of possible paths grows extremely fast. The time complexity is roughly O(n!) or worse depending on graph structure, with O(n) recursion space. This approach mainly helps build intuition about exploring graph paths but becomes infeasible even for small graphs.

Approach 2: BFS with Bitmask State Compression (O(n * 2^n))

The optimal solution models the problem as a shortest path search on an expanded state space. Instead of tracking only the current node, the state becomes (node, mask) where mask is a bitmask representing which nodes have been visited. A bit i in the mask is set if node i has already been visited. This compresses the visited set into an integer and allows efficient transitions.

Initialize a multi‑source Breadth‑First Search by pushing every node into the queue with its own mask (1 << node). BFS expands level by level, ensuring the first time we reach a state where the mask equals (1 << n) - 1 (all nodes visited) is the shortest path length. For each step, iterate through the current node’s neighbors and update the mask using nextMask = mask | (1 << neighbor). A visited structure prevents revisiting the same (node, mask) pair.

This approach combines ideas from bitmask state compression and shortest path search in graphs. The number of states is n * 2^n, and each edge transition is processed once per state. Time complexity is O(n * 2^n) and space complexity is also O(n * 2^n) due to the visited state table and queue.

The same concept can also be interpreted as a dynamic programming over subsets problem similar to Traveling Salesman. The BFS formulation is usually simpler because it directly computes the shortest number of edges while implicitly performing dynamic programming over bitmask states.

Recommended for interviews: BFS with bitmask state compression is the expected solution. It demonstrates understanding of graph traversal, state compression, and shortest path modeling. Mentioning the brute force exploration first shows problem analysis, but implementing the BFS + bitmask approach shows strong algorithmic skill.