Path visiting all nodes

The idea here is to do a depth-first search from all ‘N’ nodes and try all possible paths that visit all the nodes in the given graph. Out of all possible paths that start from any node ‘i’ and end at any node ‘j’, where ‘i’ and ‘j’ are from 0 to ‘N’ - 1 inclusive, we will take the path that has the shortest length, i.e., the path with the minimum number of edges and visits all the ‘N’ nodes in the given graph.

Algorithm:

• Declare a 2 - Dimensional array of integers, say ‘adjList’,  to store the adjacency list of the given graph.
• Build the adjacency list using the ‘edges’ array given in the problem.
• Declare an integer, say ‘minLength’, to store the length of the shortest path that visits all the ‘N’ nodes in the given graph and initialize it with 2 * ‘N’
• Declare an ‘N’ bit integer, say ‘visited’, where the i-th bit denotes whether the i-th node is visited or not, and initialize it with 0.
• Declare a 2 - Dimensional array of booleans, say ‘inProcess’, of size N * 2 ^ N, to avoid cycles during the depth-first search and initialize it with false.
• Run a loop for ‘i’ from 0 to ‘N’ - 1
  • Declare an integer, say ‘currVisited’, and initialize it with ‘visited’.
  • Mark the i-th bit of ‘currVisited’ as 1.
  • Call the ‘depthFirstSearch’ function with ‘i’, ‘currVisited’, ‘inProcess’ and ‘adjList’ as arguments, and store its returned value in ‘currLength’
  • Update ‘minLength’ as the minimum of ‘minLength’ and ‘currLength’.
• Return the maximum of ‘minLength’ - 1 and 0.

Description of ‘depthFirstSearch’ function

This function is used to traverse the given graph and find the length of the shortest path that visits all the ‘N’ nodes.

This function will take four parameters :

• node: An integer denoting the node in the given graph.
• visited: An ‘N’ bit integer denoting the visited nodes.
• inProcess: A 2 - Dimensional array of booleans to avoid cycles.
• adjList: A 2 - Dimensional array of integers denoting the adjacency list of the given graph.

int depthFirstSearch(node, visited, inProcess, adjList)

• If all the bits of ‘visited’ is 1, then return 0.
• Declare an integer, say ‘minLength’, to store the length of the shortest path that visits all the ‘N’ nodes in the given graph and initialize it with 2 * ‘N’
• If  ‘inProcess[node][visited]’ is false:
  • Mark ‘inProcess[node][visited]’ as true.
  • Run a loop for ‘i’ from 0 to the size of adjList[node] - 1
    • Declare an integer, say ‘currVisited’, and initialize it with ‘visited’.
    • Mark the ‘node’ bit of ‘currVisited’ as 1.
    • Call the ‘depthFirstSearch’ function with ‘adjList[node][i]’, ‘currVisited’, ‘inProcess’ and ‘adjList’ as arguments, and store its returned value in ‘currLength’.
    • Update ‘minLength’ as the minimum of ‘minLength’ and ‘currLength’ + 1.
  • Mark ‘inProcess[node][visited]’ as false.
• Return ‘minLength’

The idea here is to do a breadth-first search from all the ‘N’ nodes and return the length of the path(number of edges in that path) that visits all the ‘N’ nodes first, since the given graph is unweighted, doing a breadth-first search from any node ‘i’ to any node ‘j’, where ‘i’ and ‘j’ are from 0 to ‘N’ - 1 inclusive, will give the shortest path between node ‘i’ and ‘j’(refer to this).

Algorithm:

• Declare the following things:
• A 2 - Dimensional array of integers, say ‘adjList’,  to store the adjacency list of the given graph.
• A queue of an array to keep track of the current node and the nodes visited during the breadth-first search.
• A 2 - Dimensional array of integers say ‘distance’, of size N * 2 ^ N, to store the number of edges traversed to reach a particular state in breadth-first search and initialize it with 2 * N.
• An ‘N’ bit integer, say ‘visited’, where the i-th bit denotes whether the i-th node is visited or not, and initialize it with 0.
• Build the adjacency list using the ‘edges’ array given in the problem.
• Run a loop for ‘i’ from 0 to ‘N’ - 1
  • Declare an integer, say ‘currVisited’, and initialize it with ‘visited’.
  • Mark the i-th bit of ‘currVisited’ as 1.
  • Insert ‘currVisited’ and ‘i’ into the queue
  • Make ‘distance[currVisited][i]’ equal to 0
• Declare an integer say ‘answer’ to store the length of the shortest path that visits all ‘N’ nodes and initialize it with 0.
• Run a loop while the queue is not empty:
  • Declare an array of integers say ‘currState’ and initialize it with the front element of the queue.
  • Remove the front element of the queue.
  • Declare an integer say ‘currNode’ to store the current node.
  • Assign ‘currState[0]’ to ‘visited’ and ‘currState[1]’ to ‘currNode’.
  • If all the bits of ‘visited’ is 1.
    • Assign ‘distance[visited][currNode]’ to ‘answer’ i.e., do answer = distance[visited][currNode].
    • Break the loop as all bits of ‘visited’ are 1, as 1 shows we have visited all nodes of the graph.
  • Run a loop for ‘i’ from 0 to the size of adjList[currNode] - 1.
    • Declare an integer say ‘currVisited’ and initialize it with ‘visited’.
    • Mark the ‘adjList[currNode][i]’ bit of ‘currVisited’ as 1.
    • If ‘distance[visited][currNode]’ + 1  is less than ‘distance[currVisited][adjList[currNode][i]]’.
      • Insert ‘currVisited’ and ‘adjList[currNode][i]’ into the queue.
      • Update ‘distance[currVisited][adjList[currNode][i]]’ as ‘distance[currVisited][adjList[currNode][i]]’ = distance[visited][currNode] + 1.
• Return ‘answer’.

The idea here is to use iterative dynamic programming. We will calculate answers from bottom to top. Each state of the dp can be represented as the subset of nodes visited till now plus the current node. We will create a 2 - Dimensional array ‘dp[2 ^ N][N]’ where dp[visited][currNode] will store the length of the shortest path that visits the ‘visited’ subset of nodes and starts from ‘currNode’.  

Algorithm:

• Declare the following things:
• A 2 - Dimensional array of integers, say ‘adjList’,  to store the adjacency list of the given graph.
• A 2 - Dimensional array of integers say ‘dp’, of size (2 ^ N) * N, where ‘dp[i][j]’ will represent the length of the shortest path that visits ‘i’ subsets of nodes and starts from node ‘j’, and initialize it with 2 * N.
• Build the adjacency list using the ‘edges’ array given in the problem.
• Run a loop for ‘i’ from 0 to ‘N’ - 1.
  • Declare an integer, say ‘currVisited’, and initialize it with 0.
  • Mark the i-th bit of ‘currVisited’ as 1.
  • Make ‘dp[currVisited][i]’ equal to 0, since the length of the shortest path that starts from node 'i' and visits only node 'i' is 0.
• Run a loop for ‘visited’ from 0 to 2 ^ N - 1:
  • Declare a boolean variable, say ‘isImproving’ to check if we can improve the length of the shortest that starts from any node and visits the 'visited' subset of nodes, and initialize it with true.
  • Run a loop while ‘isImproving’ is true.
    • Mark ‘isImproving’ as false.
    • Run a loop for ‘startNode’ from 0 to ‘N’ - 1.
      • Run a loop for ‘i’ from 0 to size of adjList[startNode] - 1.
        • Declare an integer ‘nextNode’ and initialize it with ‘adjList[startNode][i]’.
        • Declare an integer say ‘currVisited’ and initialize it with ‘visited’.
        • Mark the ‘nextNode’ bit of ‘currVisited’ as 1.
        • If ‘dp[visited][startNode]’ + 1  is less than ‘dp[currVisited][nextNode]’.
          • Update ‘dp[currVisited][nextNode]’ as ‘dp[currVisited][nextNode]’ =  ‘dp[visited][startNode]’ + 1, as we are improving the length of the shortest path
          • If ‘currVisited’ is the same as ‘visited’
            • Mark ‘isImproving’ as true.
• Declare an integer say ‘answer’ to store the length of the shortest path that visits all ‘N’ nodes and initialize it with 2 *  N.
• Declare an integer say ‘allVisited’ and initialize it with 2 ^ N - 1, as it will have all ‘N’ bits as 1.
• Run a loop for ‘i’ from 0 to ‘N’ - 1
  • Update ‘answer’ as the minimum of ‘answer’ and ‘dp[allVisited][i], as we can start from any node 'i'.
• Return ‘answer’.