// C++ program to solve Traveling Salesman Problem   // using Branch and Bound.   #include          using     namespace     std  ;   const     int     N     =     4  ;   // final_path[] stores the final solution ie the   // path of the salesman.   int     final_path  [  N  +  1  ];   // visited[] keeps track of the already visited nodes   // in a particular path   bool     visited  [  N  ];   // Stores the final minimum weight of shortest tour.   int     final_res     =     INT_MAX  ;   // Function to copy temporary solution to   // the final solution   void     copyToFinal  (  int     curr_path  [])   {      for     (  int     i  =  0  ;     i   <  N  ;     i  ++  )      final_path  [  i  ]     =     curr_path  [  i  ];      final_path  [  N  ]     =     curr_path  [  0  ];   }   // Function to find the minimum edge cost   // having an end at the vertex i   int     firstMin  (  int     adj  [  N  ][  N  ]     int     i  )   {      int     min     =     INT_MAX  ;      for     (  int     k  =  0  ;     k   <  N  ;     k  ++  )      if     (  adj  [  i  ][  k  ]   <  min     &&     i     !=     k  )      min     =     adj  [  i  ][  k  ];      return     min  ;   }   // function to find the second minimum edge cost   // having an end at the vertex i   int     secondMin  (  int     adj  [  N  ][  N  ]     int     i  )   {      int     first     =     INT_MAX       second     =     INT_MAX  ;      for     (  int     j  =  0  ;     j   <  N  ;     j  ++  )      {      if     (  i     ==     j  )      continue  ;      if     (  adj  [  i  ][  j  ]      <=     first  )      {      second     =     first  ;      first     =     adj  [  i  ][  j  ];      }      else     if     (  adj  [  i  ][  j  ]      <=     second     &&      adj  [  i  ][  j  ]     !=     first  )      second     =     adj  [  i  ][  j  ];      }      return     second  ;   }   // function that takes as arguments:   // curr_bound -> lower bound of the root node   // curr_weight-> stores the weight of the path so far   // level-> current level while moving in the search   // space tree   // curr_path[] -> where the solution is being stored which   // would later be copied to final_path[]   void     TSPRec  (  int     adj  [  N  ][  N  ]     int     curr_bound       int     curr_weight        int     level       int     curr_path  [])   {      // base case is when we have reached level N which      // means we have covered all the nodes once      if     (  level  ==  N  )      {      // check if there is an edge from last vertex in      // path back to the first vertex      if     (  adj  [  curr_path  [  level  -1  ]][  curr_path  [  0  ]]     !=     0  )      {      // curr_res has the total weight of the      // solution we got      int     curr_res     =     curr_weight     +      adj  [  curr_path  [  level  -1  ]][  curr_path  [  0  ]];      // Update final result and final path if      // current result is better.      if     (  curr_res      <     final_res  )      {      copyToFinal  (  curr_path  );      final_res     =     curr_res  ;      }      }      return  ;      }      // for any other level iterate for all vertices to      // build the search space tree recursively      for     (  int     i  =  0  ;     i   <  N  ;     i  ++  )      {      // Consider next vertex if it is not same (diagonal      // entry in adjacency matrix and not visited      // already)      if     (  adj  [  curr_path  [  level  -1  ]][  i  ]     !=     0     &&      visited  [  i  ]     ==     false  )      {      int     temp     =     curr_bound  ;      curr_weight     +=     adj  [  curr_path  [  level  -1  ]][  i  ];      // different computation of curr_bound for      // level 2 from the other levels      if     (  level  ==  1  )      curr_bound     -=     ((  firstMin  (  adj       curr_path  [  level  -1  ])     +      firstMin  (  adj       i  ))  /  2  );      else      curr_bound     -=     ((  secondMin  (  adj       curr_path  [  level  -1  ])     +      firstMin  (  adj       i  ))  /  2  );      // curr_bound + curr_weight is the actual lower bound      // for the node that we have arrived on      // If current lower bound  < final_res we need to explore      // the node further      if     (  curr_bound     +     curr_weight      <     final_res  )      {      curr_path  [  level  ]     =     i  ;      visited  [  i  ]     =     true  ;      // call TSPRec for the next level      TSPRec  (  adj       curr_bound       curr_weight       level  +  1        curr_path  );      }      // Else we have to prune the node by resetting      // all changes to curr_weight and curr_bound      curr_weight     -=     adj  [  curr_path  [  level  -1  ]][  i  ];      curr_bound     =     temp  ;      // Also reset the visited array      memset  (  visited       false       sizeof  (  visited  ));      for     (  int     j  =  0  ;     j   <=  level  -1  ;     j  ++  )      visited  [  curr_path  [  j  ]]     =     true  ;      }      }   }   // This function sets up final_path[]    void     TSP  (  int     adj  [  N  ][  N  ])   {      int     curr_path  [  N  +  1  ];      // Calculate initial lower bound for the root node      // using the formula 1/2 * (sum of first min +      // second min) for all edges.      // Also initialize the curr_path and visited array      int     curr_bound     =     0  ;      memset  (  curr_path       -1       sizeof  (  curr_path  ));      memset  (  visited       0       sizeof  (  curr_path  ));      // Compute initial bound      for     (  int     i  =  0  ;     i   <  N  ;     i  ++  )      curr_bound     +=     (  firstMin  (  adj       i  )     +      secondMin  (  adj       i  ));      // Rounding off the lower bound to an integer      curr_bound     =     (  curr_bound  &  1  )  ?     curr_bound  /  2     +     1     :      curr_bound  /  2  ;      // We start at vertex 1 so the first vertex      // in curr_path[] is 0      visited  [  0  ]     =     true  ;      curr_path  [  0  ]     =     0  ;      // Call to TSPRec for curr_weight equal to      // 0 and level 1      TSPRec  (  adj       curr_bound       0       1       curr_path  );   }   // Driver code   int     main  ()   {      //Adjacency matrix for the given graph      int     adj  [  N  ][  N  ]     =     {     {  0       10       15       20  }      {  10       0       35       25  }      {  15       35       0       30  }      {  20       25       30       0  }      };      TSP  (  adj  );      printf  (  'Minimum cost : %d  n  '       final_res  );      printf  (  'Path Taken : '  );      for     (  int     i  =  0  ;     i   <=  N  ;     i  ++  )      printf  (  '%d '       final_path  [  i  ]);      return     0  ;   }   

   // Java program to solve Traveling Salesman Problem   // using Branch and Bound.   import     java.util.*  ;   class   GFG   {          static     int     N     =     4  ;      // final_path[] stores the final solution ie the      // path of the salesman.      static     int     final_path  []     =     new     int  [  N     +     1  ]  ;      // visited[] keeps track of the already visited nodes      // in a particular path      static     boolean     visited  []     =     new     boolean  [  N  ]  ;      // Stores the final minimum weight of shortest tour.      static     int     final_res     =     Integer  .  MAX_VALUE  ;      // Function to copy temporary solution to      // the final solution      static     void     copyToFinal  (  int     curr_path  []  )      {      for     (  int     i     =     0  ;     i      <     N  ;     i  ++  )      final_path  [  i  ]     =     curr_path  [  i  ]  ;      final_path  [  N  ]     =     curr_path  [  0  ]  ;      }      // Function to find the minimum edge cost      // having an end at the vertex i      static     int     firstMin  (  int     adj  [][]       int     i  )      {      int     min     =     Integer  .  MAX_VALUE  ;      for     (  int     k     =     0  ;     k      <     N  ;     k  ++  )      if     (  adj  [  i  ][  k  ]      <     min     &&     i     !=     k  )      min     =     adj  [  i  ][  k  ]  ;      return     min  ;      }      // function to find the second minimum edge cost      // having an end at the vertex i      static     int     secondMin  (  int     adj  [][]       int     i  )      {      int     first     =     Integer  .  MAX_VALUE       second     =     Integer  .  MAX_VALUE  ;      for     (  int     j  =  0  ;     j   <  N  ;     j  ++  )      {      if     (  i     ==     j  )      continue  ;      if     (  adj  [  i  ][  j  ]      <=     first  )      {      second     =     first  ;      first     =     adj  [  i  ][  j  ]  ;      }      else     if     (  adj  [  i  ][  j  ]      <=     second     &&      adj  [  i  ][  j  ]     !=     first  )      second     =     adj  [  i  ][  j  ]  ;      }      return     second  ;      }      // function that takes as arguments:      // curr_bound -> lower bound of the root node      // curr_weight-> stores the weight of the path so far      // level-> current level while moving in the search      // space tree      // curr_path[] -> where the solution is being stored which      // would later be copied to final_path[]      static     void     TSPRec  (  int     adj  [][]       int     curr_bound       int     curr_weight        int     level       int     curr_path  []  )      {      // base case is when we have reached level N which      // means we have covered all the nodes once      if     (  level     ==     N  )      {      // check if there is an edge from last vertex in      // path back to the first vertex      if     (  adj  [  curr_path  [  level     -     1  ]][  curr_path  [  0  ]]     !=     0  )      {      // curr_res has the total weight of the      // solution we got      int     curr_res     =     curr_weight     +      adj  [  curr_path  [  level  -  1  ]][  curr_path  [  0  ]]  ;          // Update final result and final path if      // current result is better.      if     (  curr_res      <     final_res  )      {      copyToFinal  (  curr_path  );      final_res     =     curr_res  ;      }      }      return  ;      }      // for any other level iterate for all vertices to      // build the search space tree recursively      for     (  int     i     =     0  ;     i      <     N  ;     i  ++  )      {      // Consider next vertex if it is not same (diagonal      // entry in adjacency matrix and not visited      // already)      if     (  adj  [  curr_path  [  level  -  1  ]][  i  ]     !=     0     &&      visited  [  i  ]     ==     false  )      {      int     temp     =     curr_bound  ;      curr_weight     +=     adj  [  curr_path  [  level     -     1  ]][  i  ]  ;      // different computation of curr_bound for      // level 2 from the other levels      if     (  level  ==  1  )      curr_bound     -=     ((  firstMin  (  adj       curr_path  [  level     -     1  ]  )     +      firstMin  (  adj       i  ))  /  2  );      else      curr_bound     -=     ((  secondMin  (  adj       curr_path  [  level     -     1  ]  )     +      firstMin  (  adj       i  ))  /  2  );      // curr_bound + curr_weight is the actual lower bound      // for the node that we have arrived on      // If current lower bound  < final_res we need to explore      // the node further      if     (  curr_bound     +     curr_weight      <     final_res  )      {      curr_path  [  level  ]     =     i  ;      visited  [  i  ]     =     true  ;      // call TSPRec for the next level      TSPRec  (  adj       curr_bound       curr_weight       level     +     1        curr_path  );      }      // Else we have to prune the node by resetting      // all changes to curr_weight and curr_bound      curr_weight     -=     adj  [  curr_path  [  level  -  1  ]][  i  ]  ;      curr_bound     =     temp  ;      // Also reset the visited array      Arrays  .  fill  (  visited    false  );      for     (  int     j     =     0  ;     j      <=     level     -     1  ;     j  ++  )      visited  [  curr_path  [  j  ]]     =     true  ;      }      }      }      // This function sets up final_path[]       static     void     TSP  (  int     adj  [][]  )      {      int     curr_path  []     =     new     int  [  N     +     1  ]  ;      // Calculate initial lower bound for the root node      // using the formula 1/2 * (sum of first min +      // second min) for all edges.      // Also initialize the curr_path and visited array      int     curr_bound     =     0  ;      Arrays  .  fill  (  curr_path       -  1  );      Arrays  .  fill  (  visited       false  );      // Compute initial bound      for     (  int     i     =     0  ;     i      <     N  ;     i  ++  )      curr_bound     +=     (  firstMin  (  adj       i  )     +      secondMin  (  adj       i  ));      // Rounding off the lower bound to an integer      curr_bound     =     (  curr_bound  ==  1  )  ?     curr_bound  /  2     +     1     :      curr_bound  /  2  ;      // We start at vertex 1 so the first vertex      // in curr_path[] is 0      visited  [  0  ]     =     true  ;      curr_path  [  0  ]     =     0  ;      // Call to TSPRec for curr_weight equal to      // 0 and level 1      TSPRec  (  adj       curr_bound       0       1       curr_path  );      }          // Driver code      public     static     void     main  (  String  []     args  )         {      //Adjacency matrix for the given graph      int     adj  [][]     =     {{  0       10       15       20  }      {  10       0       35       25  }      {  15       35       0       30  }      {  20       25       30       0  }     };      TSP  (  adj  );      System  .  out  .  printf  (  'Minimum cost : %dn'       final_res  );      System  .  out  .  printf  (  'Path Taken : '  );      for     (  int     i     =     0  ;     i      <=     N  ;     i  ++  )         {      System  .  out  .  printf  (  '%d '       final_path  [  i  ]  );      }      }   }   /* This code contributed by PrinciRaj1992 */   

   # Python3 program to solve    # Traveling Salesman Problem using    # Branch and Bound.   import   math   maxsize   =   float  (  'inf'  )   # Function to copy temporary solution   # to the final solution   def   copyToFinal  (  curr_path  ):   final_path  [:  N   +   1  ]   =   curr_path  [:]   final_path  [  N  ]   =   curr_path  [  0  ]   # Function to find the minimum edge cost    # having an end at the vertex i   def   firstMin  (  adj     i  ):   min   =   maxsize   for   k   in   range  (  N  ):   if   adj  [  i  ][  k  ]    <   min   and   i   !=   k  :   min   =   adj  [  i  ][  k  ]   return   min   # function to find the second minimum edge    # cost having an end at the vertex i   def   secondMin  (  adj     i  ):   first     second   =   maxsize     maxsize   for   j   in   range  (  N  ):   if   i   ==   j  :   continue   if   adj  [  i  ][  j  ]    <=   first  :   second   =   first   first   =   adj  [  i  ][  j  ]   elif  (  adj  [  i  ][  j  ]    <=   second   and   adj  [  i  ][  j  ]   !=   first  ):   second   =   adj  [  i  ][  j  ]   return   second   # function that takes as arguments:   # curr_bound -> lower bound of the root node   # curr_weight-> stores the weight of the path so far   # level-> current level while moving   # in the search space tree   # curr_path[] -> where the solution is being stored   # which would later be copied to final_path[]   def   TSPRec  (  adj     curr_bound     curr_weight     level     curr_path     visited  ):   global   final_res   # base case is when we have reached level N    # which means we have covered all the nodes once   if   level   ==   N  :   # check if there is an edge from   # last vertex in path back to the first vertex   if   adj  [  curr_path  [  level   -   1  ]][  curr_path  [  0  ]]   !=   0  :   # curr_res has the total weight   # of the solution we got   curr_res   =   curr_weight   +   adj  [  curr_path  [  level   -   1  ]]   [  curr_path  [  0  ]]   if   curr_res    <   final_res  :   copyToFinal  (  curr_path  )   final_res   =   curr_res   return   # for any other level iterate for all vertices   # to build the search space tree recursively   for   i   in   range  (  N  ):   # Consider next vertex if it is not same    # (diagonal entry in adjacency matrix and    # not visited already)   if   (  adj  [  curr_path  [  level  -  1  ]][  i  ]   !=   0   and   visited  [  i  ]   ==   False  ):   temp   =   curr_bound   curr_weight   +=   adj  [  curr_path  [  level   -   1  ]][  i  ]   # different computation of curr_bound    # for level 2 from the other levels   if   level   ==   1  :   curr_bound   -=   ((  firstMin  (  adj     curr_path  [  level   -   1  ])   +   firstMin  (  adj     i  ))   /   2  )   else  :   curr_bound   -=   ((  secondMin  (  adj     curr_path  [  level   -   1  ])   +   firstMin  (  adj     i  ))   /   2  )   # curr_bound + curr_weight is the actual lower bound    # for the node that we have arrived on.   # If current lower bound  < final_res    # we need to explore the node further   if   curr_bound   +   curr_weight    <   final_res  :   curr_path  [  level  ]   =   i   visited  [  i  ]   =   True   # call TSPRec for the next level   TSPRec  (  adj     curr_bound     curr_weight     level   +   1     curr_path     visited  )   # Else we have to prune the node by resetting    # all changes to curr_weight and curr_bound   curr_weight   -=   adj  [  curr_path  [  level   -   1  ]][  i  ]   curr_bound   =   temp   # Also reset the visited array   visited   =   [  False  ]   *   len  (  visited  )   for   j   in   range  (  level  ):   if   curr_path  [  j  ]   !=   -  1  :   visited  [  curr_path  [  j  ]]   =   True   # This function sets up final_path   def   TSP  (  adj  ):   # Calculate initial lower bound for the root node    # using the formula 1/2 * (sum of first min +    # second min) for all edges. Also initialize the    # curr_path and visited array   curr_bound   =   0   curr_path   =   [  -  1  ]   *   (  N   +   1  )   visited   =   [  False  ]   *   N   # Compute initial bound   for   i   in   range  (  N  ):   curr_bound   +=   (  firstMin  (  adj     i  )   +   secondMin  (  adj     i  ))   # Rounding off the lower bound to an integer   curr_bound   =   math  .  ceil  (  curr_bound   /   2  )   # We start at vertex 1 so the first vertex    # in curr_path[] is 0   visited  [  0  ]   =   True   curr_path  [  0  ]   =   0   # Call to TSPRec for curr_weight    # equal to 0 and level 1   TSPRec  (  adj     curr_bound     0     1     curr_path     visited  )   # Driver code   # Adjacency matrix for the given graph   adj   =   [[  0     10     15     20  ]   [  10     0     35     25  ]   [  15     35     0     30  ]   [  20     25     30     0  ]]   N   =   4   # final_path[] stores the final solution    # i.e. the // path of the salesman.   final_path   =   [  None  ]   *   (  N   +   1  )   # visited[] keeps track of the already   # visited nodes in a particular path   visited   =   [  False  ]   *   N   # Stores the final minimum weight   # of shortest tour.   final_res   =   maxsize   TSP  (  adj  )   print  (  'Minimum cost :'     final_res  )   print  (  'Path Taken : '     end   =   ' '  )   for   i   in   range  (  N   +   1  ):   print  (  final_path  [  i  ]   end   =   ' '  )   # This code is contributed by ng24_7   

   // C# program to solve Traveling Salesman Problem   // using Branch and Bound.   using     System  ;   public     class     GFG     {      static     int     N     =     4  ;      // final_path[] stores the final solution ie the      // path of the salesman.      static     int  []     final_path     =     new     int  [  N     +     1  ];      // visited[] keeps track of the already visited nodes      // in a particular path      static     bool  []     visited     =     new     bool  [  N  ];      // Stores the final minimum weight of shortest tour.      static     int     final_res     =     Int32  .  MaxValue  ;      // Function to copy temporary solution to      // the final solution      static     void     copyToFinal  (  int  []     curr_path  )      {      for     (  int     i     =     0  ;     i      <     N  ;     i  ++  )      final_path  [  i  ]     =     curr_path  [  i  ];      final_path  [  N  ]     =     curr_path  [  0  ];      }      // Function to find the minimum edge cost      // having an end at the vertex i      static     int     firstMin  (  int  [     ]     adj       int     i  )      {      int     min     =     Int32  .  MaxValue  ;      for     (  int     k     =     0  ;     k      <     N  ;     k  ++  )      if     (  adj  [  i       k  ]      <     min     &&     i     !=     k  )      min     =     adj  [  i       k  ];      return     min  ;      }      // function to find the second minimum edge cost      // having an end at the vertex i      static     int     secondMin  (  int  [     ]     adj       int     i  )      {      int     first     =     Int32  .  MaxValue       second     =     Int32  .  MaxValue  ;      for     (  int     j     =     0  ;     j      <     N  ;     j  ++  )     {      if     (  i     ==     j  )      continue  ;      if     (  adj  [  i       j  ]      <=     first  )     {      second     =     first  ;      first     =     adj  [  i       j  ];      }      else     if     (  adj  [  i       j  ]      <=     second      &&     adj  [  i       j  ]     !=     first  )      second     =     adj  [  i       j  ];      }      return     second  ;      }      // function that takes as arguments:      // curr_bound -> lower bound of the root node      // curr_weight-> stores the weight of the path so far      // level-> current level while moving in the search      // space tree      // curr_path[] -> where the solution is being stored      // which      // would later be copied to final_path[]      static     void     TSPRec  (  int  [     ]     adj       int     curr_bound        int     curr_weight       int     level        int  []     curr_path  )      {      // base case is when we have reached level N which      // means we have covered all the nodes once      if     (  level     ==     N  )     {      // check if there is an edge from last vertex in      // path back to the first vertex      if     (  adj  [  curr_path  [  level     -     1  ]     curr_path  [  0  ]]      !=     0  )     {      // curr_res has the total weight of the      // solution we got      int     curr_res     =     curr_weight      +     adj  [  curr_path  [  level     -     1  ]      curr_path  [  0  ]];      // Update final result and final path if      // current result is better.      if     (  curr_res      <     final_res  )     {      copyToFinal  (  curr_path  );      final_res     =     curr_res  ;      }      }      return  ;      }      // for any other level iterate for all vertices to      // build the search space tree recursively      for     (  int     i     =     0  ;     i      <     N  ;     i  ++  )     {      // Consider next vertex if it is not same      // (diagonal entry in adjacency matrix and not      // visited already)      if     (  adj  [  curr_path  [  level     -     1  ]     i  ]     !=     0      &&     visited  [  i  ]     ==     false  )     {      int     temp     =     curr_bound  ;      curr_weight     +=     adj  [  curr_path  [  level     -     1  ]     i  ];      // different computation of curr_bound for      // level 2 from the other levels      if     (  level     ==     1  )      curr_bound      -=     ((  firstMin  (  adj        curr_path  [  level     -     1  ])      +     firstMin  (  adj       i  ))      /     2  );      else      curr_bound      -=     ((  secondMin  (  adj        curr_path  [  level     -     1  ])      +     firstMin  (  adj       i  ))      /     2  );      // curr_bound + curr_weight is the actual      // lower bound for the node that we have      // arrived on If current lower bound  <      // final_res we need to explore the node      // further      if     (  curr_bound     +     curr_weight      <     final_res  )     {      curr_path  [  level  ]     =     i  ;      visited  [  i  ]     =     true  ;      // call TSPRec for the next level      TSPRec  (  adj       curr_bound       curr_weight        level     +     1       curr_path  );      }      // Else we have to prune the node by      // resetting all changes to curr_weight and      // curr_bound      curr_weight     -=     adj  [  curr_path  [  level     -     1  ]     i  ];      curr_bound     =     temp  ;      // Also reset the visited array      Array  .  Fill  (  visited       false  );      for     (  int     j     =     0  ;     j      <=     level     -     1  ;     j  ++  )      visited  [  curr_path  [  j  ]]     =     true  ;      }      }      }      // This function sets up final_path[]      static     void     TSP  (  int  [     ]     adj  )      {      int  []     curr_path     =     new     int  [  N     +     1  ];      // Calculate initial lower bound for the root node      // using the formula 1/2 * (sum of first min +      // second min) for all edges.      // Also initialize the curr_path and visited array      int     curr_bound     =     0  ;      Array  .  Fill  (  curr_path       -  1  );      Array  .  Fill  (  visited       false  );      // Compute initial bound      for     (  int     i     =     0  ;     i      <     N  ;     i  ++  )      curr_bound      +=     (  firstMin  (  adj       i  )     +     secondMin  (  adj       i  ));      // Rounding off the lower bound to an integer      curr_bound     =     (  curr_bound     ==     1  )     ?     curr_bound     /     2     +     1      :     curr_bound     /     2  ;      // We start at vertex 1 so the first vertex      // in curr_path[] is 0      visited  [  0  ]     =     true  ;      curr_path  [  0  ]     =     0  ;      // Call to TSPRec for curr_weight equal to      // 0 and level 1      TSPRec  (  adj       curr_bound       0       1       curr_path  );      }      // Driver code      static     public     void     Main  ()      {      // Adjacency matrix for the given graph      int  [     ]     adj     =     {     {     0       10       15       20     }      {     10       0       35       25     }      {     15       35       0       30     }      {     20       25       30       0     }     };      TSP  (  adj  );      Console  .  WriteLine  (  'Minimum cost : '     +     final_res  );      Console  .  Write  (  'Path Taken : '  );      for     (  int     i     =     0  ;     i      <=     N  ;     i  ++  )     {      Console  .  Write  (  final_path  [  i  ]     +     ' '  );      }      }   }   // This code is contributed by Rohit Pradhan   

   const     N     =     4  ;   // final_path[] stores the final solution ie the   // path of the salesman.      let     final_path     =     Array     (  N     +     1  ).  fill     (  -  1  );       // visited[] keeps track of the already visited nodes   // in a particular path      let     visited     =     Array     (  N  ).  fill     (  false  );   // Stores the final minimum weight of shortest tour.      let     final_res     =     Number  .  MAX_SAFE_INTEGER  ;   // Function to copy temporary solution to   // the final solution   function     copyToFinal     (  curr_path  ){      for     (  let     i     =     0  ;     i      <     N  ;     i  ++  ){      final_path  [  i  ]     =     curr_path  [  i  ];      }      final_path  [  N  ]     =     curr_path  [  0  ];   }   // Function to find the minimum edge cost   // having an end at the vertex i   function     firstMin     (  adj       i  ){   let     min     =     Number  .  MAX_SAFE_INTEGER  ;      for     (  let     k     =     0  ;     k      <     N  ;     k  ++  ){      if     (  adj  [  i  ][  k  ]      <     min     &&     i     !==     k  ){      min     =     adj  [  i  ][  k  ];      }      }      return     min  ;   }   // function to find the second minimum edge cost   // having an end at the vertex i   function     secondMin     (  adj       i  ){      let     first     =     Number  .  MAX_SAFE_INTEGER  ;      let     second     =     Number  .  MAX_SAFE_INTEGER  ;      for     (  let     j     =     0  ;     j      <     N  ;     j  ++  ){      if     (  i     ==     j  ){      continue  ;      }      if     (  adj  [  i  ][  j  ]      <=     first  ){      second     =     first  ;      first     =     adj  [  i  ][  j  ];      }      else     if     (  adj  [  i  ][  j  ]      <=     second     &&     adj  [  i  ][  j  ]     !==     first  ){      second     =     adj  [  i  ][  j  ];      }      }      return     second  ;   }   // function that takes as arguments:   // curr_bound -> lower bound of the root node   // curr_weight-> stores the weight of the path so far   // level-> current level while moving in the search   // space tree   // curr_path[] -> where the solution is being stored which   // would later be copied to final_path[]      function     TSPRec     (  adj       curr_bound       curr_weight       level       curr_path  )   {       // base case is when we have reached level N which   // means we have covered all the nodes once      if     (  level     ==     N  )      {         // check if there is an edge from last vertex in      // path back to the first vertex      if     (  adj  [  curr_path  [  level     -     1  ]][  curr_path  [  0  ]]     !==     0  )      {          // curr_res has the total weight of the      // solution we got      let     curr_res     =      curr_weight     +     adj  [  curr_path  [  level     -     1  ]][  curr_path  [  0  ]];          // Update final result and final path if      // current result is better.      if     (  curr_res      <     final_res  )      {      copyToFinal     (  curr_path  );      final_res     =     curr_res  ;      }      }      return  ;       }          // for any other level iterate for all vertices to      // build the search space tree recursively      for     (  let     i     =     0  ;     i      <     N  ;     i  ++  ){          // Consider next vertex if it is not same (diagonal      // entry in adjacency matrix and not visited      // already)      if     (  adj  [  curr_path  [  level     -     1  ]][  i  ]     !==     0     &&     !  visited  [  i  ]){          let     temp     =     curr_bound  ;      curr_weight     +=     adj  [  curr_path  [  level     -     1  ]][  i  ];          // different computation of curr_bound for      // level 2 from the other levels      if     (  level     ==     1  ){      curr_bound     -=     (  firstMin     (  adj       curr_path  [  level     -     1  ])     +     firstMin     (  adj       i  ))     /     2  ;       }      else      {      curr_bound     -=     (  secondMin     (  adj       curr_path  [  level     -     1  ])     +     firstMin     (  adj       i  ))     /     2  ;       }          // curr_bound + curr_weight is the actual lower bound      // for the node that we have arrived on      // If current lower bound  < final_res we need to explore      // the node further      if     (  curr_bound     +     curr_weight      <     final_res  ){      curr_path  [  level  ]     =     i  ;      visited  [  i  ]     =     true  ;         // call TSPRec for the next level      TSPRec     (  adj       curr_bound       curr_weight       level     +     1       curr_path  );       }          // Else we have to prune the node by resetting      // all changes to curr_weight and curr_bound      curr_weight     -=     adj  [  curr_path  [  level     -     1  ]][  i  ];      curr_bound     =     temp  ;          // Also reset the visited array      visited  .  fill     (  false  )         for     (  var     j     =     0  ;     j      <=     level     -     1  ;     j  ++  )      visited  [  curr_path  [  j  ]]     =     true  ;       }       }   }      // This function sets up final_path[]       function     TSP     (  adj  )   {       let     curr_path     =     Array     (  N     +     1  ).  fill     (  -  1  );       // Calculate initial lower bound for the root node   // using the formula 1/2 * (sum of first min +   // second min) for all edges.   // Also initialize the curr_path and visited array      let     curr_bound     =     0  ;       visited  .  fill     (  false  );          // compute initial bound      for     (  let     i     =     0  ;     i      <     N  ;     i  ++  ){      curr_bound     +=     firstMin     (  adj       i  )     +     secondMin     (  adj       i  );          }          // Rounding off the lower bound to an integer      curr_bound     =     curr_bound     ==     1     ?     (  curr_bound     /     2  )     +     1     :     (  curr_bound     /     2  );       // We start at vertex 1 so the first vertex   // in curr_path[] is 0      visited  [  0  ]     =     true  ;       curr_path  [  0  ]     =     0  ;       // Call to TSPRec for curr_weight equal to   // 0 and level 1      TSPRec     (  adj       curr_bound       0       1       curr_path  );   }   //Adjacency matrix for the given graph      let     adj     =  [[  0       10       15       20  ]         [  10       0       35       25  ]      [  15       35       0       30  ]      [  20       25       30       0  ]];       TSP     (  adj  );       console  .  log     (  `Minimum cost:  ${  final_res  }  `  );   console  .  log     (  `Path Taken:  ${  final_path  .  join     (  ' '  )  }  `  );      // This code is contributed by anskalyan3.