Min Cost to Visit Every Node - Dynamic Programming / Bitmask

Problems
1

https://algo.monster/problems/min_cost_to_visit_every_node

2

Before looking at the solution, it would be good to research more about the problem and checkout the regular DP solution. Bitmask is cool though.

3

Explained nicely in this video: https://www.youtube.com/watch?v=iQBxxTZDajU

4

Implemented with necessary details

int dfs(int bitmaskPath, int cur, vector<vector<int>> & graph, vector<vector<int>> &dp) {
    int nbits = (1 << graph.size()) - 1;
    if(bitmaskPath == nbits) return 0;
    if(dp[bitmaskPath][cur] != 0) return dp[bitmaskPath][cur];
    int ans = INF;
    for(int i = 0; i < graph[cur].size(); i++){
        int visitedPath = bitmaskPath & 1 << i;
        if(visitedPath == 0 && graph[cur][i]) {
            int nextbits = bitmaskPath | (1 << i);
            ans = min(ans, graph[cur][i] + dfs(nextbits, i, graph, dp));
        }
    }
    return dp[bitmaskPath][cur] = ans;
}

int min_cost_to_visit_every_node(std::vector<std::vector<int>> graph) {
    // WRITE YOUR BRILLIANT CODE HERE
    int m = graph.size();
    
    //return bfs(graph);
    int bitmask = 1 << 0;
    vector<vector<int>> dp(1 << m, vector<int> (m, 0));
    int ans = dfs(bitmask, 0, graph, dp);
    return ans == INF ? -1 : ans;
}
5

Test Case#6, I can find path:
0->2->4->3->1->3->7->5->9->4->8->2->6
and get cost 1230 smaller than expected output 1328.
Could anyone verify or explain?

6

I didn’t check the costs but your path is visiting node 3 twice. The Traveling Salesman problem asks for visiting each node exactly once. This should be better explained in the problem statement.

7

Great video! But I think that problem has some key differences from this one (undirected, connected, may revisit nodes)

8

The problem should specify we are visiting each node once. Otherwise, the solution doesn’t work for a graph like

[
[0, 1, 1],
[1, 0, 0],
[1, 0, 0]
]

If we are allowed to visit a node more than once, there is a solution with 1->2->1->3. Otherwise there isn’t.

9

In case someone is wondering how the solution would look like, without using bitmask, I want to leave the implementation using boolean[ ] here. I found it easier to use a boolean[] to keep track of state, just like we do for various other backtracking/DP problems, and then change the implementation to use a bitmask.

     public static int minCostToVisitEveryNode(List<List<Integer>> graph) {
            boolean[] visited = new boolean[graph.size()];
            visited[0] = true;
            int ans = topDown(graph, visited, 0);
            return (ans == Integer.MAX_VALUE) ? -1 : ans;
      }
    
    public static int topDown(List<List<Integer>> graph, 
                              boolean[] visited, 
                              int currentNodeIndex) {
        
        // "visited" represents the visited nodes in the path that we're currently traversing
        // minimum cost itself is computed by "aggregation" strategy
        // See https://algo.monster/problems/backtracking-aggregation
        
        // base case - have I visited all nodes?
        boolean isVisitedAll = true;
        for (int i = 0; i < visited.length; i++) {
            isVisitedAll = isVisitedAll && visited[i];
        }
        
        if (isVisitedAll) {
            return 0;
        }
        
        List<Integer> neighbors = graph.get(currentNodeIndex);
        
        // "ans" represents what's the minimum cost to reach all the nodes from currentNodeIndex
        // given the nodes already reached (expressed as "visited" array)
        //
        // initializing to Integer.MAX; this is to represent scenarios where visiting all nodes is NOT possible
        // BUT, this can overflow, if we add other edge costs
        // Handled that while doing Math.min down below
        int ans = Integer.MAX_VALUE;
        
        for (int i=0; i < neighbors.size(); i++) {
            int neighborEdge = neighbors.get(i);
            if (neighborEdge == 0) {
                // there is no edge, so continue
                continue;
            }
            
            if (!visited[i]) {
                // if this neighbor is NOT visited yet in this path
                // find minimum cost to reach all nodes, 
                // by adding neighbor to the path represented by "visited"
                visited[i] = true;
                int resultFromNeighbor = topDown(graph, visited, i);
                ans = Math.min(ans, (resultFromNeighbor == Integer.MAX_VALUE) 
                                           ? Integer.MAX_VALUE 
                                           : (neighborEdge + resultFromNeighbor));
                
                // Undo, since the same node could be visited in another path through currentNodeIndex
                visited[i] = false;
            }
        }
        
        return ans;
    }