travelling salesman problem solution using dynamic programming

• Data Structures & Algorithms
• DSA - Overview
• DSA - Environment Setup
• DSA - Algorithms Basics
• DSA - Asymptotic Analysis
• Data Structures
• DSA - Data Structure Basics
• DSA - Data Structures and Types
• DSA - Array Data Structure
• Linked Lists
• DSA - Linked List Data Structure
• DSA - Doubly Linked List Data Structure
• DSA - Circular Linked List Data Structure
• Stack & Queue
• DSA - Stack Data Structure
• DSA - Expression Parsing
• DSA - Queue Data Structure
• Searching Algorithms
• DSA - Searching Algorithms
• DSA - Linear Search Algorithm
• DSA - Binary Search Algorithm
• DSA - Interpolation Search
• DSA - Jump Search Algorithm
• DSA - Exponential Search
• DSA - Fibonacci Search
• DSA - Sublist Search
• DSA - Hash Table
• Sorting Algorithms
• DSA - Sorting Algorithms
• DSA - Bubble Sort Algorithm
• DSA - Insertion Sort Algorithm
• DSA - Selection Sort Algorithm
• DSA - Merge Sort Algorithm
• DSA - Shell Sort Algorithm
• DSA - Heap Sort
• DSA - Bucket Sort Algorithm
• DSA - Counting Sort Algorithm
• DSA - Radix Sort Algorithm
• DSA - Quick Sort Algorithm
• Graph Data Structure
• DSA - Graph Data Structure
• DSA - Depth First Traversal
• DSA - Breadth First Traversal
• DSA - Spanning Tree
• Tree Data Structure
• DSA - Tree Data Structure
• DSA - Tree Traversal
• DSA - Binary Search Tree
• DSA - AVL Tree
• DSA - Red Black Trees
• DSA - B Trees
• DSA - B+ Trees
• DSA - Splay Trees
• DSA - Tries
• DSA - Heap Data Structure
• DSA - Recursion Algorithms
• DSA - Tower of Hanoi Using Recursion
• DSA - Fibonacci Series Using Recursion
• Divide and Conquer
• DSA - Divide and Conquer
• DSA - Max-Min Problem
• DSA - Strassen's Matrix Multiplication
• DSA - Karatsuba Algorithm
• Greedy Algorithms
• DSA - Greedy Algorithms
• DSA - Travelling Salesman Problem (Greedy Approach)
• DSA - Prim's Minimal Spanning Tree
• DSA - Kruskal's Minimal Spanning Tree
• DSA - Dijkstra's Shortest Path Algorithm
• DSA - Map Colouring Algorithm
• DSA - Fractional Knapsack Problem
• DSA - Job Sequencing with Deadline
• DSA - Optimal Merge Pattern Algorithm
• Dynamic Programming
• DSA - Dynamic Programming
• DSA - Matrix Chain Multiplication
• DSA - Floyd Warshall Algorithm
• DSA - 0-1 Knapsack Problem
• DSA - Longest Common Subsequence Algorithm
• DSA - Travelling Salesman Problem (Dynamic Approach)
• Approximation Algorithms
• DSA - Approximation Algorithms
• DSA - Vertex Cover Algorithm
• DSA - Set Cover Problem
• DSA - Travelling Salesman Problem (Approximation Approach)
• Randomized Algorithms
• DSA - Randomized Algorithms
• DSA - Randomized Quick Sort Algorithm
• DSA - Karger’s Minimum Cut Algorithm
• DSA - Fisher-Yates Shuffle Algorithm
• DSA Useful Resources
• DSA - Questions and Answers
• DSA - Quick Guide
• DSA - Useful Resources
• DSA - Discussion
• Selected Reading
• UPSC IAS Exams Notes
• Developer's Best Practices
• Questions and Answers
• Effective Resume Writing
• HR Interview Questions
• Computer Glossary

Travelling Salesman Problem (Dynamic Approach)

Travelling salesman dynamic programming algorithm, implementation.

Travelling salesman problem is the most notorious computational problem. We can use brute-force approach to evaluate every possible tour and select the best one. For n number of vertices in a graph, there are (n−1)! number of possibilities. Thus, maintaining a higher complexity.

However, instead of using brute-force, using the dynamic programming approach will obtain the solution in lesser time, though there is no polynomial time algorithm.

Let us consider a graph G = (V,E) , where V is a set of cities and E is a set of weighted edges. An edge e(u, v) represents that vertices u and v are connected. Distance between vertex u and v is d(u, v) , which should be non-negative.

Suppose we have started at city 1 and after visiting some cities now we are in city j . Hence, this is a partial tour. We certainly need to know j , since this will determine which cities are most convenient to visit next. We also need to know all the cities visited so far, so that we don't repeat any of them. Hence, this is an appropriate sub-problem.

For a subset of cities S $\epsilon$ {1,2,3,...,n} that includes 1 , and j $\epsilon$ S, let C(S, j) be the length of the shortest path visiting each node in S exactly once, starting at 1 and ending at j .

When |S|> 1 , we define 𝑪 C(S,1)= $\propto$ since the path cannot start and end at 1.

Now, let express C(S, j) in terms of smaller sub-problems. We need to start at 1 and end at j . We should select the next city in such a way that

$$C\left ( S,j \right )\, =\, min\, C\left ( S\, -\, \left\{j \right\},i \right )\, +\, d\left ( i,j \right )\: where\: i\: \epsilon \: S\: and\: i\neq j$$

There are at the most 2 n .n sub-problems and each one takes linear time to solve. Therefore, the total running time is O(2 n .n 2 ) .

In the following example, we will illustrate the steps to solve the travelling salesman problem.

From the above graph, the following table is prepared.

$$Cost\left ( 2,\Phi ,1 \right )\, =\, d\left ( 2,1 \right )\,=\,5$$

$$Cost\left ( 3,\Phi ,1 \right )\, =\, d\left ( 3,1 \right )\, =\, 6$$

$$Cost\left ( 4,\Phi ,1 \right )\, =\, d\left ( 4,1 \right )\, =\, 8$$

$$Cost(i,s)=min\left\{Cos\left ( j,s-(j) \right )\, +\,d\left [ i,j \right ] \right\}$$

$$Cost(2,\left\{3 \right\},1)=d[2,3]\, +\, Cost\left ( 3,\Phi ,1 \right )\, =\, 9\, +\, 6\, =\, 15$$

$$Cost(2,\left\{4 \right\},1)=d[2,4]\, +\, Cost\left ( 4,\Phi ,1 \right )\, =\, 10\, +\, 8\, =\, 18$$

$$Cost(3,\left\{2 \right\},1)=d[3,2]\, +\, Cost\left ( 2,\Phi ,1 \right )\, =\, 13\, +\, 5\, =\, 18$$

$$Cost(3,\left\{4 \right\},1)=d[3,4]\, +\, Cost\left ( 4,\Phi ,1 \right )\, =\, 12\, +\, 8\, =\, 20$$

$$Cost(4,\left\{3 \right\},1)=d[4,3]\, +\, Cost\left ( 3,\Phi ,1 \right )\, =\, 9\, +\, 6\, =\, 15$$

$$Cost(4,\left\{2 \right\},1)=d[4,2]\, +\, Cost\left ( 2,\Phi ,1 \right )\, =\, 8\, +\, 5\, =\, 13$$

$$Cost(2,\left\{3,4 \right\},1)=min\left\{\begin{matrix} d\left [ 2,3 \right ]\,+ \,Cost\left ( 3,\left\{ 4\right\},1 \right )\, =\, 9\, +\, 20\, =\, 29 \\ d\left [ 2,4 \right ]\,+ \,Cost\left ( 4,\left\{ 3\right\},1 \right )\, =\, 10\, +\, 15\, =\, 25 \\ \end{matrix}\right.\, =\,25$$

$$Cost(3,\left\{2,4 \right\},1)=min\left\{\begin{matrix} d\left [ 3,2 \right ]\,+ \,Cost\left ( 2,\left\{ 4\right\},1 \right )\, =\, 13\, +\, 18\, =\, 31 \\ d\left [ 3,4 \right ]\,+ \,Cost\left ( 4,\left\{ 2\right\},1 \right )\, =\, 12\, +\, 13\, =\, 25 \\ \end{matrix}\right.\, =\,25$$

$$Cost(4,\left\{2,3 \right\},1)=min\left\{\begin{matrix} d\left [ 4,2 \right ]\,+ \,Cost\left ( 2,\left\{ 3\right\},1 \right )\, =\, 8\, +\, 15\, =\, 23 \\ d\left [ 4,3 \right ]\,+ \,Cost\left ( 3,\left\{ 2\right\},1 \right )\, =\, 9\, +\, 18\, =\, 27 \\ \end{matrix}\right.\, =\,23$$

$$Cost(1,\left\{2,3,4 \right\},1)=min\left\{\begin{matrix} d\left [ 1,2 \right ]\,+ \,Cost\left ( 2,\left\{ 3,4\right\},1 \right )\, =\, 10\, +\, 25\, =\, 35 \\ d\left [ 1,3 \right ]\,+ \,Cost\left ( 3,\left\{ 2,4\right\},1 \right )\, =\, 15\, +\, 25\, =\, 40 \\ d\left [ 1,4 \right ]\,+ \,Cost\left ( 4,\left\{ 2,3\right\},1 \right )\, =\, 20\, +\, 23\, =\, 43 \\ \end{matrix}\right.\, =\, 35$$

The minimum cost path is 35.

Start from cost {1, {2, 3, 4}, 1}, we get the minimum value for d [1, 2]. When s = 3, select the path from 1 to 2 (cost is 10) then go backwards. When s = 2, we get the minimum value for d [4, 2]. Select the path from 2 to 4 (cost is 10) then go backwards.

When s = 1, we get the minimum value for d [4, 2] but 2 and 4 is already selected. Therefore, we select d [4, 3] (two possible values are 15 for d [2, 3] and d [4, 3], but our last node of the path is 4). Select path 4 to 3 (cost is 9), then go to s = ϕ step. We get the minimum value for d [3, 1] (cost is 6).

Following are the implementations of the above approach in various programming languages −

• [email protected]

What’s New ?

The Top 10 favtutor Features You Might Have Overlooked

• Don’t have an account Yet? Sign Up

Remember me Forgot your password?

• Already have an Account? Sign In

Lost your password? Please enter your email address. You will receive a link to create a new password.

Back to log-in

By Signing up for Favtutor, you agree to our Terms of Service & Privacy Policy.

Travelling Salesman Problem using Dynamic Programming

• Jun 17, 2023
• 7 Minutes Read
• Why Trust Us We uphold a strict editorial policy that emphasizes factual accuracy, relevance, and impartiality. Our content is crafted by top technical writers with deep knowledge in the fields of computer science and data science, ensuring each piece is meticulously reviewed by a team of seasoned editors to guarantee compliance with the highest standards in educational content creation and publishing.
• By Harshita Rajput

Imagine you have to go to a party in another city and return back home as soon as possible. Which algorithm will you apply to reach your home so that you cover the shortest distance? Let us understand Travelling Salesman Problem in this guide.

What is Traveling Salesman Problem?

The Traveling Salesman Problem classic optimization problem in Computer Science. There is a salesman who wants to travel over a number of cities and he has to return back to the original city he started from and he has the choice to start from any of the cities he wants to. During his journey, we need to minimize the total distance traveled by him. 

Here is the main problem statement:

" We will be given a graph that will be represented in the form of an adjacency matrix, say distance, that denotes the distance between 2 cities, say, i and j. The distance[i][j] denotes the distance between 2 cities if the value of dist[i][j] == 0; this implies the given cities are not connected i.e. no direct edge exists between them. We can start from any node and we need to return to the original city through the shortest distance covering all the cities. "

So, basically, we need to complete a cycle in this question, and such a cycle is known as the Hamiltonian cycle. A Hamiltonian cycle is a set of edges such that every node is visited only once and we come back to the original position. So in short, in this problem, we need to return a minimum weight Hamiltonian cycle. We just have to minimize the total cost of the cycle.

Let's first try to get a Hamiltonian cycle with minimum weight from the graph below. Given the following graph and the distance between cities he has traveled, let's find out the shortest path in which he can travel all the cities.

The Hamiltonian cycle with min weight can be:

How does the Algorithm Work?

Let's take an example of a graph say:

• As we have an option to start from any position, we start from A.
• Making a recursion tree and using bit masking. 

As 4 cities are there, the bit mask here would be = 0000 (at the beginning) respectively denoting D, C, B, and A  cities. The bit shows 0 for a particular city if it has not been visited and 1 if already been visited. So if bit mask = 1111 that means all bits are set, which implies all cities have been visited and we can denote this by 1<

We try to find the possible options that exist. This can be done by iterating over the adjacency matrix of A or the other way of doing so can be iterating over other cities and checking if they can be a possible option to travel from A. As we begin, we visit city A, and the bit mask value is now changed to 0001.

Each of these recursive branches denotes one path.

Now, as we move forward from A to B, we add the distance in a variable, say, ans. And we mark city B as visited.

We add the distance to the answer. Now we only visit the cities from B that aren't visited yet so we have 2 options available C and D.

We then move to C and then to D while marking them visited and adding the cost to the and. Now here, we have explored each unvisited city. So now we backtrack, while marking each city as unvisited and go to the original city if a direct edge between them exists. As there is a direct edge from D to A and C to A, the nodes return the cost required to go back to the original source.

This way we explore each available option from the starting node. We also maintain a minimum cost variable that maintains the minimum cost spent to visit each city and return to the original city.

The recursion tree would look like this:

Traveling Salesman Algorithm

Here is the algorithm for Travelling Salesman Problem:

• Define the mask as (1<<n)-1.
• Create a function, say, tsp() having mask and city as arguments. As the mask denotes a set of cities visited so far, we iterate over the mask and get to know which city isn't visited.
• The base case is when we visit all the cities i.e. mask has all of its bits set, we return the distance between the current city and the original city.
• If the city is not visited, we make recursive calls by adding the distance of the original city and the city not visited and try to get the distance remaining from recursive calls
• In the recursive call, we pass a mask with the current city visited and the current city.

Travelling Salesman Problem in Java

Here is the complete Java Program to implement Travelling Salesman Problem:

Time & Space Complexity 

Here we have fixed the source node as we get the same answer whether we start from A or B or any other node because of that cyclic permutation in this case.

The time complexity of the Travelling Salesman Problem comes out to be O(n-1!). The space complexity of this code comes out to be O(n).

Now we can notice that this bitmask can only have 2^n values ranging from 0000 to 1111. The city can take n values. So the total number of distinct states comes out to be (2^n )* n. Also in this approach, some sub-problems were getting overlapped.

To optimize this approach, we use DP. We will create a 2D DP table of the values and we memorize all the results for the given value of mask and city.

Optimized Approach using Dynamic Programming

Here is the simple way to implement the Optimized Approach using Dynamic Programming. Initially we make a 2D array of [2^n][n] and initially put -1 at each position as initially, all states have values = -1.

To avoid overlapping subproblems i.e. avoiding a state which has already been computed, we check dp[bitMask][city]. If this comes out to be -1, implies the city hasn't been visited, else the city has already been visited and we return dp[bitMask][city] = ans.

Here is the Java Code for Travelling Salesman Problem using Dynamic Programming:

The time complexity comes out to be O(n ^2 * (2*n)). As we are using an extra space of (2^n) *n. The space complexity comes out to be O((2^n) *n).

Conclusion 

Travelling Salesman is a classic problem demanding in-depth knowledge of graphs and DP. It is an NP-hard problem. The optimization used in this problem can be implemented in other questions of this type too. This problem is necessary from the interview point of view, so I hope you all understood it well!

FavTutor - 24x7 Live Coding Help from Expert Tutors!

About The Author

Harshita Rajput

More by favtutor blogs, monte carlo simulations in r (with examples), aarthi juryala.

The unlist() Function in R (with Examples)

Paired Sample T-Test using R (with Examples)

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications You must be signed in to change notification settings

Solve travelling salesman problem using dynamic programming.

kristiansandratama/travelling-salesman-problem-dynamic-programming

Folders and files, repository files navigation, travelling salesman problem using dynamic programming.

This repository contains an implementation of dynamic programming to find the shortest path from the travelling salesman problem (TSP). In this case, the salesman needs to visit each city once without returning to the start city.

Getting Started

Replace the distance_matrix variable value with the distances between each pair of cities in square matrix form.

Then pick a start city.

To run the python program, execute this command in terminal.

• Python 100.0%

• Interview Q

DAA Tutorial

Asymptotic analysis, analysis of sorting, divide and conquer, lower bound theory, sorting in linear time, binary search trees, red black tree, dynamic programming, greedy algorithm, backtracking, shortest path, all-pairs shortest paths, maximum flow, sorting networks, complexity theory, approximation algo, string matching.

Interview Questions

• Send your Feedback to [email protected]

Help Others, Please Share

Learn Latest Tutorials

Transact-SQL

Reinforcement Learning

R Programming

React Native

Python Design Patterns

Python Pillow

Python Turtle

Preparation

Verbal Ability

Company Questions

Trending Technologies

Artificial Intelligence

Cloud Computing

Data Science

Machine Learning

B.Tech / MCA

Data Structures

Operating System

Computer Network

Compiler Design

Computer Organization

Discrete Mathematics

Ethical Hacking

Computer Graphics

Software Engineering

Web Technology

Cyber Security

C Programming

Control System

Data Mining

Data Warehouse

• Interview Problems on DP
• Practice DP
• Tutorial on Dynamic Programming
• Optimal Substructure
• Overlapping Subproblem
• Memoization
• Tabulation vs Memoization
• 0/1 Knapsack
• Unbounded Knapsack
• Coin Change
• Egg Dropping Puzzle
• Matrix Chain Multiplication
• Palindrome Partitioning
• DP on Arrays
• DP with Bitmasking
• DP on Trees
• DP on Graph

Bitmasking and Dynamic Programming | Travelling Salesman Problem

In this post, we will be using our knowledge of dynamic programming and Bitmasking technique to solve one of the famous NP-hard problem “Traveling Salesman Problem”. Before solving the problem, we assume that the reader has the knowledge of   

• DP and formation of DP transition relation
• Bitmasking in DP
• Traveling Salesman problem

To understand this concept lets consider the below problem :  Problem Description :   

The above problem is the well-known Travelling Salesman Problem. The first part is to calculate the minimum distance between the two cells. We can do it by simply using a BFS as all the distances are unit distance. To optimize our solution we will be pre-calculating the distances taking the initial location and the location of the houses as the source point for our BFS. Each BFS traversal takes O(size of grid) time. Therefore, it is O(X * size_of_grid) for overall pre-calculation, where X = number of houses + 1 (initial position) Now let’s think of a DP state   So we will be needing to track the visited houses and the last visited house to uniquely identify a state in this problem. Therefore, we will be taking dp[index][mask] as our DP state.   

Here,  index : tells us the location of current house mask : tells us the houses that are visited ( if ith bit is set in mask then this means that the ith dirty tile is cleaned)   

Whereas dp[index][mask] will tell us the minimum distance to visit X(number of set bits in mask) houses corresponding to their order of their occurrence in the mask where the last visited house is house at location index. State transition relation So our initial state will be dp[0][0] this tells that we are currently at initial tile that is our initial location and mask is 0 that states that no house is visited till now. And our final destination state will be dp[any index][LIMIT_MASK] , here LIMIT_MASK = (1<<N) – 1   and N = number of houses. Therefore our DP state transition can be stated as   

The above relation can be visualized as the minimum distance to visit all the houses by standing at curr_idx house and by already visiting cur_mask houses is equal to min of distance between the curr_idx house and idx house + minimum distance to visit all the houses by standing at idx house and by already  visiting ( cur_mask | (1 <<idx) ) houses. So, here we iterate over all possible idx values such that cur_mask has i th bit as 0 that tells us that i th house is not visited. Whenever we have our mask = LIMIT_MASK, this means that we have visited all the houses in the town. So, we will add the distance from the last visited town (i.e the town at cur_idx position) to the initial position (0, 0). The C++ program for the above implementation is given below:  

The given grid :  . . . . . * .  . . . # . . .  . * . # . * .  . . . . . . .  Minimum distance for the given grid : 16 The given grid :  . . . # . . .  . . . # . * .  . . . # . . .  . * . # . * .  . . . # . . .  Minimum distance for the given grid : not possible

Output:   

Note : We have used the initial state to be dp[0][1] because we have pushed the start location at the first position in the container of houses. Hence, our Bit Mask will be 1 as the 0 th bit is set i.e we have visited the starting location for our trip.

Time Complexity : O(n 2 * 2 n ) Consider the number of houses to be n . So, there are n * (2 n ) states and at every state, we are looping over n houses to transit over to next state and because of memoization we are doing this looping transition only once for each state. Auxiliary space: O(n * 2 n ), due to the memoization of the dp states.

Recommended :   

• http://www.spoj.com/problems/CLEANRBT/
• https://www.youtube.com/watch?v=-JjA4BLQyqE

Please Login to comment...

Similar reads.

• Dynamic Programming
• Best PS5 SSDs in 2024: Top Picks for Expanding Your Storage
• Best Nintendo Switch Controllers in 2024
• Xbox Game Pass Ultimate: Features, Benefits, and Pricing in 2024
• Xbox Game Pass vs. Xbox Game Pass Ultimate: Which is Right for You?
• Full Stack Developer Roadmap [2024 Updated]

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Search anything:

Travelling Salesman Problem (Bitmasking and Dynamic Programming)

Algorithms graph algorithms dynamic programming (dp) bitwise algorithm.

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

In this article we will start our discussion by understanding the problem statement of The Travelling Salesman Problem perfectly and then go through the basic understanding of bit masking and dynamic programming .

What is the problem statement ?

Travelling Salesman Problem is based on a real life scenario, where a salesman from a company has to start from his own city and visit all the assigned cities exactly once and return to his home till the end of the day. The exact problem statement goes like this, "Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point."

There are two important things to be cleared about in this problem statement,

• Visit every city exactly once
• Cover the shortest path

What is the need of Dynamic Programming ?

If we look into the brute force approach for solving this problem, we can see that due to recursion call, a lot of cases are repeating themselves and that's the reason of a bigger runtime. The code for the brute force approach can be found below,

As it can be deduced easily from the above code that, the time complexity is O(n!) and the space complexity is O(n^2) . By using dynamic programming we can save the repeated cases when they are calculated for the first time, and next time when we need the result we can directly use them from our storage(in terms of data structures).

What is the need of Bit Masking ?

As you might know, computer hardwares natively support binary digits(bits) i.e. 0 for false and 1 for true. In other language we can compile that 0 means not occupied and 1 means occupied.

We can break the problem into three different parts,

• Constructing and maintaining another 2D array which stores the shortest path sum values for each (i,j), whcih means in this matrix, value at (i,j) denotes the weight of the shortest path at any instance of the program run.
• Maintaining one visited variable, which in terms denote the total possible permutations of the cities.
• Finally we will be checking if a city is visited before. We will be using bitwise & and bitwise left shift << operator to get into the solution.

Steps To Solve the Problem

There are few classical and easy steps that we must follow to solve the TSP problem,

• Finding Adjacent matrix of the graph, which will act as an input.
• performing the shortest_path algorithm with the help of bitmasking and dynamic programming, by coding out a function.
• Understanding the bitwise operators.

Step-1 - Finding Adjacent Matrix Of the Graph

You will need a two dimensional array for getting the Adjacent Matrix of the given graph. Here are the steps;

• Get the total number of nodes and total number of edges in two variables namely num_nodes and num_edges.
• Create two multidimensional arrays, edges_list having the dimension equal to num_nodes * num_nodes and dp_array having the dimension equal to total number of permutations m, which is interms equal to (1<<num_nodes). Set all the dp_array entries to -1, which will act as a check point integer in the core algorithm.
• Run a loop num_nodes time and take two inputs namely first_node and second_node * everytime as two nodes having an edge between them and place the edges_list[first_node][second_node] position equal to 1.
• Finally after the loop executes we have an adjacent matrix available i.e edges_list.

Step - 2 - Performing The Shortest Path Algorithm using Dynamic Programming and Bitmasking

The most important step in designing the core algorithm is this one, let's have a look at the pseudocode of the algorithm below. We will be considering a small example and try to understand each of the following steps.

What is a mask ?

Let's consider the following graph as an example, where we have four cities named A,B,C,D and there are six weighted edges between them as shown in the figure.

So for the salesman to cover all the cities and return to the main city, he has to visit each city once. Lets consider 4 bits for A,B,C,D where 0 in a bit represents the city is not visited and 1 represented the city is visited. So for the visited variable in the algorithm, we are considering all the citities already visited and that gives us a bit representation of 1 1 1 1 . Have a look at the following diagram.

As we can see this bit representation will give use an integer representation equal to (2^4 - 1) , which can be otherwise written as (1<<4) - 1 . The aim of using bitwise operators like leftshift instead of using pow() etc is that, bits work on a hardware level which are faster. This deduce our first step of assigning the visited variable a value which is equal to (1<<num_nodes)-1 .

The next step is to interpret the importance of mask.

mask is nothing but a checker if all the nodes/cities are visited. Suppose the salesman starts from node A. It means the value of mask will be 0 0 0 1 , which is 1 in integer format. As soon as the salesman visits B it become 0 0 1 1 . If the salesman visits C in the second and not B then it becomes 0 1 0 1 . And when he visits all the cities once, we get mask same as that of visited, i.e. 1 1 1 1 .

This serves as the base case of our algorithm. When the mask is equal to visited we retrun something. But what to return ? We will discuss next.

What is the work of position here ?

The position stores the position of the salesman at any point of time. As we are starting from city A or we may call it as source city and denote it as 0 in our adjacency matrix, the initial position is 0. The sales man moves from city 0 to city 4 and returns back to 0.

The position value varies with city with every recursive call.

When our basecase is satisfied we will return the adjacency matrix value at the (position,source_city) coordinate, which signifies the direct path value between the position and the source.

The DP array and it's usages

The work of the dp_array here is to store the minimum possible path value of two nodes i and j at the array position (i,j). The -1 value works as a checker. If the value of certain (i,j) is -1 means the weight of the shortest path has not been calculated between i and j.

Here we perform another check that if the dp_array value for (mask,position) is not equal to -1 then return the original value at that position.

The sole aim of this step is to avoid repeatation that has occured during normal recursive solution.

The normal calculataion

And here comes the final normal calculation or we can say the core calculataion for this algorithm. This calculation will only take place if the base case and the check case gets false.

• We will be maintaining a variable named ans for getting the minimum path and assign it to INT_MAX at the beginning.
• We will be calling a loop from city= 0 to the city = n
• Perform a recursive call and save the output in a integer varaible named newAns .
• Later we will be getting the minimum of ans and newAns and assigning the same to the dp_array for memorization purpose.
• Finally return the dp_array value at (mask,position).

The Total Code

Time & space complexity.

We have recursive calls here as well as loops. In fact we have recursive call inside loops.

It can be derived that the space complexity will be O(V^2) where V is the number of nodes/cities here.

For the time complexity we need to look into a little bit deeper. As we can see we have a recurrance relation here in terms of recursion, which is a subproblem and each subproblem takes linear time to get the output,i.e. O(V * 2^V) .This recursive call happens inside a loop havinbg runtime of O(V) . Hence we have a total runtime of O(V^2 * 2^V) , which is exponential.