Travelling Salesman Problem

A Quick Overview

Problem Statement

Given a set of cities and distance between every pair of cities as an adjacency matrix, the problem is to find shortest route that visits all cities exactly once and returns to starting point.

1. Let city 1 be starting point and ending point. We can consider any point as a starting point since the route is cyclic.  2. Generate all possible permutations of cities which are (n-1)!.

Simple Approach

3. Determine cost of each permutation and keep track of minimum cost permutation.  4. Return permutation with minimum cost.

Time complexity: O(N!) Here, N is number of cities. Space complexity: O(1)

Here, we calculate the cost function cost() using a dynamic approach Cost ().

Dynamic Approach

Time Complexity: O(N^2*2^N) 

1. Create two primary data holders.    - List containing indices of cities based on input matrix of distance.   - Array containing our result

Greedy Approach

2. Traverse the given adjacency matrix tsp[][] for all the cities, and update the cost if the cost of reaching any city is less than the current cost.

3. Calculate the minimum path cycle using above step and return their minimum cost.

Time complexity: O(N^2*logN)  Space complexity: O(N)

How to implement these solutions in different languages?