- Problem Statement
- Simple Approach
- Travelling Salesman Problem Using Dynamic Programming
- C Implementation of DP approach
- C++ Implementation of DP approach
- Python Implementation of DP approach
- Java Implementation of DP approach
- Greedy Approach
- C++ Implementation of Greedy Approach
- Java Implementation of Greedy Approach
- Python Implementation of Greedy Approach
- Practice Questions
- Frequently Asked Questions
Problem Statement
Given a set of cities and the distance between every pair of cities as an adjacency matrix, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point. Learn More
Travelling Salesman Problem Example 1
Input –
Output –
Travelling Salesman Problem Example 2
Input –
Output –
Minimum weight Hamiltonian Cycle: EACBDE= 32
Simple Approach
- Consider city 1 as the starting and ending point. Since the route is cyclic, we can consider any point as a starting point.
- Now, we will generate all possible permutations of cities which are (n-1)!.
- Find the cost of each permutation and keep track of the minimum cost permutation.
- Return the permutation with minimum cost.
C++ Implementation
Java Implementation
Python Implementation
Time complexity: O(N!), Where N is the number of cities.
Space complexity: O(1).
Travelling Salesman Problem Using Dynamic Programming
In travelling salesman problem algorithm, we take a subset N of the required cities that need to be visited, the distance among the cities dist, and starting city s as inputs. Each city is identified by a unique city id which we say like 1,2,3,4,5………n
Here we use a dynamic approach to calculate the cost function Cost(). Using recursive calls, we calculate the cost function for each subset of the original problem.
To calculate the cost(i) using Dynamic Programming, we need to have some recursive relation in terms of sub-problems.
We start with all subsets of size 2 and calculate C(S, i) for all subsets where S is the subset, then we calculate C(S, i) for all subsets S of size 3 and so on.
There are at most O(n2^n) subproblems, and each one takes linear time to solve. The total running time is, therefore, O(n^22^n). The time complexity is much less than O(n!) but still exponential. The space required is also exponential.
C Implementation of DP approach
C++ Implementation of DP approach
Python Implementation of DP approach
Java Implementation of DP approach
Time Complexity: O(N^2*2^N).
Greedy Approach
- First of all, we have to create two primary data holders.
- First of them is a list that can hold the indices of the cities in terms of the input matrix of distances between cities
- And the Second one is the array which is our result
- Perform traversal on the given adjacency matrix tsp[][] for all the city and if the cost of reaching any city from the current city is less than the current cost the update the cost.
- Generate the minimum path cycle using the above step and return their minimum cost.
C++ Implementation of Greedy Approach
Java Implementation of Greedy Approach
Python Implementation of Greedy Approach
Time complexity: O(N^2*logN), Where N is the number of cities.
Space complexity: O(N).
Practice Questions
Frequently Asked Questions
1. Which algorithm is used for the Travelling salesman problem?
Ans. Travelling Salesman Problem uses Dynamic programming with a masking algorithm.
2. What is the complexity of the Travelling salesman problem?
Ans.: The complexity of TSP using Greedy will be O(N^2LogN) and using DP will be O(N^22^N).
3. How is this problem modelled as a graph problem?
Ans.: The TSP can be modelled as a graph problem by considering a complete graph G = (V, E). A tour is then a circuit in G that meets every node. In this context, tours are sometimes called Hamiltonian circuits.
4: What is the difficulty level of the Travelling salesman problem?
Ans.: It is an NP-hard problem.
