Travelling Salesman Problem implementation using BackTracking | Javascript 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 ; 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
var V = 4 ; var ans = 1000000000 ; function tsp ( graph , currPos , n , count , cost ) { if ( count == n && graph [ currPos ] [ 0 ] ) { ans = Math . min ( ans , cost + graph [ currPos ] [ 0 ] ) ; return ; } for ( var i = 0 ; i < n ; i ++ ) { if ( ! v [ i ] && graph [ currPos ] [ i ] ) { v [ i ] = true ; tsp ( graph , i , n , count + 1 , cost + graph [ currPos ] [ i ] ) ; v [ i ] = false ; } } } ; var n = 4 ; var graph = [ [ 0 , 10 , 15 , 20 ] , [ 10 , 0 , 35 , 25 ] , [ 15 , 35 , 0 , 30 ] , [ 20 , 25 , 30 , 0 ] ] ; var v = Array ( n ) . fill ( false ) ; v [ 0 ] = true ; tsp ( graph , 0 , n , 1 , 0 ) ; document . write ( ans ) ;