Travelling Salesman Problem implementation using BackTracking | Java implementation of the approach ; Function to find the minimum weight Hamiltonian Cycle ; If last node is reached and it has a link to the starting node i . e the source then keep the minimum value out of the total cost of traversal and " ans " Finally return to check for more possible values ; BACKTRACKING STEP Loop to traverse the adjacency list of currPos node and increasing the count by 1 and cost by graph [ currPos , i ] value ; Mark as visited ; Mark ith node as unvisited ; Driver code ; n is the number of nodes i . e . V ; Boolean array to check if a node has been visited or not ; Mark 0 th node as visited ; Find the minimum weight Hamiltonian Cycle ; ans is the minimum weight Hamiltonian Cycle
class GFG { static int tsp ( int [ ] [ ] graph , boolean [ ] v , int currPos , int n , int count , int cost , int ans ) { if ( count == n && graph [ currPos ] [ 0 ] > 0 ) { ans = Math . min ( ans , cost + graph [ currPos ] [ 0 ] ) ; return ans ; } for ( int i = 0 ; i < n ; i ++ ) { if ( v [ i ] == false && graph [ currPos ] [ i ] > 0 ) { v [ i ] = true ; ans = tsp ( graph , v , i , n , count + 1 , cost + graph [ currPos ] [ i ] , ans ) ; v [ i ] = false ; } } return ans ; } public static void main ( String [ ] args ) { int n = 4 ; int [ ] [ ] graph = { { 0 , 10 , 15 , 20 } , { 10 , 0 , 35 , 25 } , { 15 , 35 , 0 , 30 } , { 20 , 25 , 30 , 0 } } ; boolean [ ] v = new boolean [ n ] ; v [ 0 ] = true ; int ans = Integer . MAX_VALUE ; ans = tsp ( graph , v , 0 , n , 1 , 0 , ans ) ; System . out . println ( ans ) ; } }