Travelling Salesman Problem

[kratimitra]

💥 Proposal

Hey, I am Krati Mitra (Discord username Krati(P)#8709), a GSSOC'21 participant. I want to add the code for the issue "Travelling Salesman Problem".

Task: We are given a set of cities and distances between each pair of cities, we have to find the shortest possible path visiting every city exactly once and returning to the initial city.

Input :A matrix representing the distance between each nodes

Output :The minimum cost of visiting every city once and returning to the starting point.

For example, Example #1: Input: { 0, 10, 15, 20 }, { 10, 0, 35, 25 }, { 15, 35, 0, 30 }, { 20, 25, 30, 0 } Output: 80 Explanation: The path can be 1-2-4-3-1. The cost of the tour is 10+25+30+15 = 80.

I can contribute to solve this issue using C++.

This problem can be solved using Naive Approach with time complexity of O (n^n) BackTracking with time complexity of O(n!).

I'll try to inculcate this approach in my code. Please assign me this task @HarshCasper .

Thank You

Have you read the Contributing Guidelines on Pull Requests

Yes

[github-actions[bot]]

Hello @kratimitra,
Thank you for opening an issue. :partying_face:
To get assigned to this particular issue please use /assign
Check this guide before contributing.

[kratimitra]

/assign

[github-actions[bot]]

This issue has been assigned to @kratimitra! It will become unassigned if it isn't closed within 21 days. A maintainer can also add the pinned label to prevent it from being unassigned.