CODEWITHSUNDEEP
algorithm
Ouais
Ouais

Reputation: 371

What's the difference between Minimmum Spanning Tree and Travelling Salesman Problems

Can we solve the Traveling Salesman Problem by finding the Minimum Spanning Tree?

Upvotes: 22

Views: 20832

Answers (2)

Yakov Galka
Yakov Galka

Reputation: 72539

It's the difference between

Finding an acyclic connected subgraph T of G with V(T) = V(G) and Weight(T) is minimal

and

Finding a cycle C in G such that V(C) = V(G) and Weight(C) is minimal

where Weight(X) = Sum of edges of X. As you can see these two problems are pretty different.

Yet, there is a relation between the two. If the graph weights satisfy the triangle inequality, one can use the MST to approximate the TSP within a factor of x2: compute the MST, then traverse it (from any root) and return the vertices in a pre-order. You can find the detailed analysis of this approximation (as well as other approximations) in The traveling salesman problem: An overview of exact and approximate algorithms by G Laporte - European Journal of Operational Research, 1992 - Elsevier.

Upvotes: 6

Anthony Labarre
Anthony Labarre

Reputation: 2804

The Minimum Spanning Tree problem asks you to build a tree that connects all cities and has minimum total weight, while the Travelling Salesman Problem asks you to find a trip that visits all cities with minimum total weight (and possibly coming back to your starting point).

If you're having trouble seeing the difference, in MST, you need to find a minimum weight tree in a weighted graph, while in TSP you need to find a minimum weight path (or cycle / circuit). Does that help?

Upvotes: 37

Related Questions