Travelling Salesman Problem

Question

A)250    B)300      C)550      D)375

Comments

TSP---start one vertex and visit each vertex and return to original position .

path------>a-b-c-d-e.

100+50+100+50+75=375

---

Even I had marked 375,but the answer given was 550 using Prim's Algorithm approach(nearest neighbour). So do we always have to find all possible permutation ,and then return the minimum among them?

---

yes,find all permutations.in that which one is least that is shortest path.

Correct answer is 375.

if we apply prims algorithm for TSP then time complexity of TSP is reduced to polynomial time not only TSP remaining all problems also we can solve.:D)

But this is not correct,u r answer is absolutely correct.

---

Thanks :)

Answer 1

The answer is 375 , a-b-c-d-e

 We basically brute force search through all possible paths and pick the cheapest one , in this case its 375.

Answer 2

This can be done by brute force but no of path will be (n-1)!/2. From the choose the path of minimum length.

Else you can apply Floyed warshall Algortihm to calculate the path cost taken by the salesman. Which turn out to be 375.

 

Note : Here I read few of the comment which were saying that Kruskal or Primis can be applied to calulate the TSP  but it is wrong as we all know that Kruskal and Prims create a Minimum Spanning Tree(Not path, Tree can have branches where we are finding optimal path for n-1 vertex and adding our starting vertex and the start and end to create a cycle.)