[FEATURE REQUEST] Adding the Travelling Salesman Problem

[DBasu2610]

What would you like to Propose?

Problem Statement: Given a set of cities and the distances between each pair, the objective is to find the shortest possible route that visits each city exactly once and returns to the starting point.

Input: A list of cities and the distance (or cost) between each pair of cities.

Output: The shortest route that covers all cities once and returns to the start.

Type: NP-hard problem, meaning it's computationally difficult to find an exact solution for larger inputs in polynomial time.

Brute Force Approach: Check all possible permutations of cities (factorial time complexity, O(n!)).

Dynamic Programming Approach: More efficient than brute force, using memoization to store intermediate results (O(n² * 2ⁿ)).

Approximation Algorithms: Used for larger instances, such as the Nearest Neighbor and Christofides' Algorithm.

So, we would use the Dynamic Programming Approach since it is more efficient.

Issue details

Problem Statement: Given a set of cities and the distances between each pair, the objective is to find the shortest possible route that visits each city exactly once and returns to the starting point.

Test Case Input: Number of cities: 4 Distance matrix:

0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0 Explanation: There are 4 cities numbered from 0 to 3. The distance between each pair of cities is represented in the matrix, where dist[i][j] is the distance between city i and city j. For example:

Distance from city 0 to city 1 is 10. Distance from city 0 to city 2 is 15. Distance from city 1 to city 3 is 25, and so on. Expected Output: The minimum cost of the tour is: 80

Shortest Path: The optimal path is: 0 → 1 → 3 → 2 → 0, with a total distance of 80.

Additional Information

No response

[Chickoo16]

Hi @DBasu2610 could you assign this issue to me. I would like to contribute.

[siriak]

Sounds good, let's add it

[Nandinig24]

Please assign the task to me

[Aastha-ojha-20]

please assign this issue to me

[keshavkhetan123]

please assign this task to me

[santycarbahol]

Adding the Travelling Salesman Problem

What would you like to Propose? For this project, I'd like to create a tree or an algorithm that can determine the short path, such as BFS or DFS, which would compare the distance between cities and choose the shortest route.

Issue details Problem Statement: Given a set of cities and the distances between each pair, the objective is to find the shortest possible route that visits each city exactly once and returns to the starting point.

Additional Information No more additional information

[FEATURE REQUEST] Adding the Travelling Salesman Problem https://github.com/TheAlgorithms/Java/issues/5564

[janmejay484]

/assign

[Krushit-Babariya]

Hii @DBasu2610, I want to contribute in it..!!

[github-actions[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contribution!

[github-actions[bot]]

Please reopen this issue once you have made the required changes. If you need help, feel free to ask in our Discord server or ping one of the maintainers here. Thank you for your contribution!