Shortest Path Visiting All Nodes Solution in C++

Navigate to Other Solutions

Problem Description

Ah, the classic “Shortest Path Visiting All Nodes” problem! Imagine you’re a kid in a candy store, and you want to taste every single candy without missing a single one. But wait! The store has a maze-like layout, and you can only visit each candy once. Sounds fun, right? Well, that’s exactly what this problem is about! You have a graph (the candy store) and you need to find the shortest path that visits all nodes (candies) at least once.

In more technical terms, given a graph represented as an adjacency list, your task is to find the shortest path that visits every node in the graph. The catch? You can start from any node. So, no pressure!

Code Solution

class Solution {
 public:
  int shortestPathLength(vector>& graph) {
    const int n = graph.size();
    const int goal = (1 << n) - 1;
    queue> q;  // (u, state)
    vector> seen(n, vector(1 << n));

    for (int i = 0; i < n; ++i)
      q.emplace(i, 1 << i);

    for (int step = 0; !q.empty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        const auto [u, state] = q.front();
        q.pop();
        if (state == goal)
          return step;
        if (seen[u][state])
          continue;
        seen[u][state] = true;
        for (const int v : graph[u])
          q.emplace(v, state | 1 << v);
      }

    return -1;
  }
};

Approach

The approach used in this solution is a classic breadth-first search (BFS) combined with bit manipulation. The idea is to maintain a queue that tracks the current node and the state of visited nodes using a bitmask. Each time we visit a node, we update the state to reflect that. When the state matches the goal (all nodes visited), we return the number of steps taken.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n * 2ⁿ)
Space Complexity	O(n * 2ⁿ)

Real-World Example

Imagine you're a delivery driver who needs to deliver packages to every house in a neighborhood. You want to minimize your driving distance while ensuring that you visit every house at least once. This problem is akin to the "Shortest Path Visiting All Nodes" problem, where your goal is to find the most efficient route that covers all destinations (houses) without retracing your steps unnecessarily.