# Min Cost to Visit Every Node - Dynamic Programming / Bitmask

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.

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

Implemented with necessary details

``````int dfs(int bitmaskPath, int cur, vector<vector<int>> & graph, vector<vector<int>> &dp) {
int nbits = (1 << graph.size()) - 1;
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));
}
}
}

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;
}
``````

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?

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.

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

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.

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;
}
``````