Input: n-points in the 2D plane. Output: Traveling Salesman route cost along with the route (Visualization is also added).
Implemented in three different ways-
Exact Exponential Method: Checked all possible permutations of nodes and found the optimal valid permutation. The code is run with different input size graph to make input size vs execution time chart and graph. Branch and bounding Method: Dasgupta algorithm is used for this method. The code is run with different input size graph to make input size vs execution time chart and graph. Greedy 2-Approximation Algorithm: MST approach is used for this method. The code is run with different input size graph to make input size vs execution time chart and graph. we can easily verify that approximation ratio is 2 from the outputs.