Daily bit(e) of C++ | Shortest path to visit all nodes
Daily bit(e) of C++ #287, Common interview problem: Shortest path to visit all nodes.
Today, we will look at a common C++ interview problem: Shortest path to visit all nodes.
Given a connected graph as an adjacency list (std::vector<std::vector<unsigned>>), return the length of the shortest path that visits all nodes.
The path may revisit nodes and edges. You can assume a computationally feasible number of nodes.
For example, in the above graph, the shortest path has a length of four.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/qz9G3zdoh.
Solution
You might be tempted to look for a solution using one of the shortest path algorithms. Unfortunately, this is a simpler version of the Traveling Salesman Problem, meaning we are dealing with an NP problem.
One approach to solve this problem would be to first pre-calculate the shortest node-node distances and then run a breadth-first search, constructing permutations of nodes. This would lead to O(n!) complexity.
A better approach is to run a simultaneous breadth-first search starting from each node. Consider that when we visit a node, we only care about which nodes we have visited. Because breadth-first search guarantees the shortest path, we don’t have to consider the order of nodes we have visited. We will find our shortest path the first time we visit all the nodes.
If we put this together, we have to keep track of the state as a tuple of the current node and a set of visited nodes, which we can track using bit flags. This leads to O(n*2^n) total states (space complexity), and plugging this into our simultaneous breadth-first search leads to overall O(n^2*2^n) time complexity.
