Shortest Path Visiting All Nodes

The problem statement is from Leetcode and is as follows:

You have an undirected, connected graph of n nodes labelled from 0 to n - 1. You are given an array graph where graph[i] is a list of all the nodes connected with node i by an edge.

Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

Example 1:

Input: graph = [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]

The basic idea of bitmask is that you convey information (typically yes/no) via the bits.

How do we know when bitmasks can be used?
Bitmasks can be used in place of sets(or boolean array) — while saving space, also, a super useful indicator that bitmasks could be used is when the input size is small(it’s 15) here.

This problem is just a simple version of the Travelling Salesman Problem, which has already been proved to be NP-Hard

What is the DP state here?

Inspired from DBabichev’s solution, the DP state here consists of 2 parts :

1. the bitmask which indicates the number of nodes visited right now.
2. the last node visited, as the next state of the mask(the next node to be visited) will typically depend on what the current position actually is.

First, we start with finding the shortest distance between any pair of nodes — which can be done by BFS or using DP — Floyd Warshall Algorithm.

Let dp be a 2D vector, dp[mask][j] means the shortest path covering nodes indicated by the mask and ending at the jth node.
Masks can range from all 0’s to all 1’s depending on whether no node has been visited or all nodes have been visited. So, the number of masks would be 2^n, n is the total number of nodes.

So, dp[1010][1], means the shortest path covering node 1 and node 3, and ending up at node 1.

W[i][j] indicates the shortest distance between node i and j, which would be pre-computed using the Floyd-Warshall algorithm.

Suppose, we have a bitmask with 4 bits set to one and remaining to zero, then the neighbour bitmask in the below equation is the bitmask with one of those 1’s set to 0.

The recursive equation for the Travelling salesman problem is:

dp[mask][j] = min(dp[mask][j] , dp[neighbor bitmask][k] + W[k][j]); 
where k is the node last visited by neighboring bitmask.

How the above equation works will be clear after reading the code comments.

The final answer would be simply min(dp[all 1's][j]), where j can vary from 0 to n — 1.

Here is the code with comments at every major step of the algorithm :

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        
        int n = graph.size();
        vector<vector<int>> W(n , vector<int>(n , 150));
        //150 is a random large number depending on the given input constraints
        for(int i = 0 ; i < n ; i++) //distance to self is zero
            W[i][i] = 0;
        
        for(int i = 0 ; i < n ; i++){ // distance to neighbor is 1 , else infi
            for(int j : graph[i]){
                W[i][j] = 1;
            }
        }
        
        
        for(int i = 0 ; i < n ; i++){ // nearest dist b/w each pair of nodes
            for(int j = 0 ; j < n ; j++){
                for(int k = 0 ; k < n ; k++){
                    W[i][j] = min(W[i][j] , W[i][k] + W[k][j]); // basically implementing the floyd warshall algo
                }
            }
        }
        
        vector<vector<int>> dp(1<<n , vector<int>(n, 150));
        
        for(int i = 0 ; i < n ; i++){
            dp[1<<i][i] = 0; // total distance after visiting one node from the same node is 0
        }
        
        for(int mask = 0 ; mask < 1<< n ; mask++){
            
            vector<int> nz;
            for(int j = 0 ; j < n; j++){
                if(mask & (1 << j))
                    nz.push_back(j); // finding pos of non-zero bits, i.e. nodes visited
            }
            
            for(int j : nz){ // j is the last node visited by mask
                for(int k : nz){//k is the node last visited by the neighbor mask
                    if(j != k){
                    int neib = dp[mask ^ (1 << j)][k]; // neighbor mask has not yet visited jth node, and it is ending up at kth node
                    dp[mask][j] = min(dp[mask][j] , neib + W[k][j]);
					//neib + W[k][j] means neighbor mask ends at kth node, and then visits jth node from k to become the current mask
                    }
                }
            }
            
        }
        
        int res = 150;
        
        for(int i = 0 ; i < n ; i++)
            res = min(res, dp.back()[i]); // finding min dist after visiting all nodes and ending at ith node
            
        return res;
    }
};

The time complexity for Floyd Warshall would be cubic, for the Travelling salesman,
so overall time complexity is clearly O(2^n * n * n) = O(n² * 2^n).

The space to hold the distance array, and the dp array are clearly O(n²) and O(2^n * n), so the space complexity is O(n * 2^n).