Travelling Salesman Problem implementation using BackTracking | Python3 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
V = 4 NEW_LINE answer = [ ] NEW_LINE def tsp ( graph , v , currPos , n , count , cost ) : NEW_LINE INDENT if ( count == n and graph [ currPos ] [ 0 ] ) : NEW_LINE INDENT answer . append ( cost + graph [ currPos ] [ 0 ] ) NEW_LINE return NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT if ( v [ i ] == False and graph [ currPos ] [ i ] ) : NEW_LINE INDENT v [ i ] = True NEW_LINE tsp ( graph , v , i , n , count + 1 , cost + graph [ currPos ] [ i ] ) NEW_LINE v [ i ] = False NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 4 NEW_LINE graph = [ [ 0 , 10 , 15 , 20 ] , [ 10 , 0 , 35 , 25 ] , [ 15 , 35 , 0 , 30 ] , [ 20 , 25 , 30 , 0 ] ] NEW_LINE v = [ False for i in range ( n ) ] NEW_LINE v [ 0 ] = True NEW_LINE tsp ( graph , v , 0 , n , 1 , 0 ) NEW_LINE print ( min ( answer ) ) NEW_LINE DEDENT