** Travelling salesman problem (TSP)** is a famous computational problem in which a salesman has to visit all the given cities, each only once and return to the starting city with the shortest possible distance. This problem is an NP-hard problem, which means that the problem gets exponentially more complex as the number of cities increases. Despite its complexity, the TSP has many practical applications, including logistics, route optimization, and DNA sequencing.

In this blog, we will discuss the TSP problem and its implementation in C, C++, Java, and Python programming languages. We will provide code snippets in each language to demonstrate the implementation.

Understanding the Travelling Salesman Problem The Travelling Salesman Problem can be represented as a graph with nodes representing the cities and edges representing the distances between them. The goal is to find the shortest path that visits each city once and returns to the starting city.

The brute force approach to solve this problem is to calculate the distances between all possible permutations of cities and select the path with the shortest distance. However, this approach is not feasible for large numbers of cities as the number of permutations increases exponentially. Therefore, several algorithms have been developed to solve the TSP problem efficiently.

Implementation of the TSP Problem in C The implementation of the TSP problem in C involves the use of the branch and bound algorithm. The branch and bound algorithm is a divide and conquer technique that solves the TSP problem by dividing it into subproblems and solving each subproblem.

Here is the code snippet for implementing the TSP problem in C:

#include <stdio.h> #include <limits.h> #define V 4 int tsp(int graph[][V], int start_vertex, int bitmask, int visited_all, int dp[][16]) { if (bitmask == visited_all) { return graph[start_vertex][0]; } if (dp[start_vertex][bitmask] != -1) { return dp[start_vertex][bitmask]; } int ans = INT_MAX; for (int i = 0; i < V; i++) { if ((bitmask & (1 << i)) == 0) { int subproblem = graph[start_vertex][i] + tsp(graph, i, bitmask | (1 << i), visited_all, dp); ans = (ans < subproblem) ? ans : subproblem; } } dp[start_vertex][bitmask] = ans; return ans; } int main() { int graph[][V] = { { 0, 10, 15, 20 }, { 10, 0, 35, 25 }, { 15, 35, 0, 30 }, { 20, 25, 30, 0 } }; int visited_all = (1 << V) - 1; int dp[V][1 << V]; for (int i = 0; i < V; i++) { for (int j = 0; j < (1 << V); j++) { dp[i][j] = -1; } } printf("The minimum distance is %d\n", tsp(graph, 0, 1, visited_all, dp)); return 0; }

Implementation of the TSP Problem in C++ The implementation of the TSP problem in C++ involves the use of the same branch and bound algorithm used in C. Here is the code snippet for implementing the TSP problem in C++:

#include <iostream> #include <vector> #include <limits.h> #define V 4 int tsp(int graph[][V], int start_vertex, int bitmask, int visited_all, int dp[][1<<V]) { // If all the cities are visited, return the distance from last city to starting city if(bitmask == visited_all) { return graph[start_vertex][0]; } // If we have already calculated the minimum distance for the current vertex and bitmask, return it if(dp[start_vertex][bitmask] != -1) { return dp[start_vertex][bitmask]; } // Set initial distance as infinity int ans = INT_MAX; // Iterate through all the cities for(int i=0; i<V; i++) { // If city i is not visited yet if((bitmask & (1<<i)) == 0) { // Calculate the distance from current city to city i and recursively find the distance for the remaining cities int subproblem = graph[start_vertex][i] + tsp(graph, i, bitmask | (1<<i), visited_all, dp); // Update the minimum distance ans = std::min(ans, subproblem); } } // Store the calculated minimum distance in the dp table dp[start_vertex][bitmask] = ans; return ans; } int main() { // Graph representation of cities and distances int graph[][V] = { { 0, 10, 15, 20 }, { 10, 0, 35, 25 }, { 15, 35, 0, 30 }, { 20, 25, 30, 0 } }; // Total number of cities int n = V; // Calculate the bitmask for all cities visited int visited_all = (1<<n) - 1; // Initialize the dp table with -1 int dp[V][1<<V]; memset(dp, -1, sizeof(dp)); // Starting city is city 0 int start_vertex = 0; // Call the tsp function and print the minimum distance std::cout << "The minimum distance is " << tsp(graph, start_vertex, 1<<start_vertex, visited_all, dp) << std::endl; return 0; }

Implementation of the TSP Problem in Java The implementation of the TSP problem in Java also involves the use of the same branch and bound algorithm used in C and C++. Here is the code snippet for implementing the TSP problem in Java:

import java.util.*; class TSP { private static int tsp(int[][] graph, int start_vertex, int bitmask, int visited_all, int[][] dp) { // If all the cities are visited, return the distance from last city to starting city if(bitmask == visited_all) { return graph[start_vertex][0]; } // If we have already calculated the minimum distance for the current vertex and bitmask, return it if(dp[start_vertex][bitmask] != -1) { return dp[start_vertex][bitmask]; } // Set initial distance as infinity int ans = Integer.MAX_VALUE; // Iterate through all the cities for(int i=0; i<graph.length; i++) { // If city i is not visited yet if((bitmask & (1<<i)) == 0) { // Calculate the distance from current city to city i and recursively find the distance for the remaining cities int subproblem = graph[start_vertex][i] + tsp(graph, i, bitmask | (1<<i), visited_all, dp); // Update the minimum distance ans = Math.min(ans, subproblem); } } // Store the calculated minimum distance in the dp table dp[start_vertex][bitmask] = ans; return ans; } public static void main(String[] args) { // Graph representation of cities and distances int[][] graph = { { 0, 10, 15, 20 }, { 10, 0, 35, 25 }, { 15, 35, 0, 30 }, { 20, 25, 30, 0 } }; // Total number of cities int n = graph.length; // Calculate the bitmask for all cities visited int visited_all = (1<<n) - 1; // Initialize the dp table with -1 int[][] dp = new int[n][1<<n]; for(int i=0; i<n; i++) { Arrays.fill(dp[i], -1); } // Starting city is city 0 int start_vertex = 0; // Call the tsp function and print the minimum distance System.out.println("The minimum distance is " + tsp(graph, start_vertex, 1<<start_vertex, visited_all, dp)); } }

Implementation of the TSP Problem in Python The implementation of the TSP problem in Python also involves the use of the same branch and bound algorithm used in C, C++, and Java. Here is the code snippet for implementing the TSP problem in Python:

import sys INT_MAX = sys.maxsize def tsp(graph, start_vertex, bitmask, visited_all, dp): # If all the cities are visited, return the distance from last city to starting city if(bitmask == visited_all): return graph[start_vertex][0] # If we have already calculated the minimum distance for the current vertex and bitmask, return it if(dp[start_vertex][bitmask] != -1): return dp[start_vertex][bitmask] # Set initial distance as infinity ans = INT_MAX # Iterate through all the cities for i in range(len(graph)): # If city i is not visited yet if((bitmask & (1<<i)) == 0): # Calculate the distance from current city to city i and recursively find the distance for the remaining cities subproblem = graph[start_vertex][i] + tsp(graph, i, bitmask | (1<<i), visited_all, dp) # Update the minimum distance ans = min(ans, subproblem) # Store the calculated minimum distance in the dp table dp[start_vertex][bitmask] = ans return ans if __name__ == '__main__': # Graph representation of cities and distances graph = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]] # Total number of cities n = len(graph) # Calculate the bitmask for all cities visited visited_all = (1<<n) - 1 # Initialize the dp table with -1 dp = [[-1]*(1<<n) for i in range(n)] # Starting city is city 0 start_vertex = 0 # Call the tsp function and print the minimum distance print("The minimum distance is", tsp(graph, start_vertex, 1<<start_vertex, visited_all, dp))

The Travelling Salesman Problem (TSP) is a famous problem in the field of computer science, which involves finding the shortest possible route that a travelling salesman can take to visit a given set of cities and return to his starting point. The problem is NP-hard, and several algorithms have been proposed to solve it. In this blog post, we have discussed one of the most popular algorithms for solving the TSP problem, which is the branch and bound algorithm. We have also provided the implementation of the TSP problem in C, C++, Java, and Python programming languages using the branch and bound algorithm.