Is the shortest edge always used in the solution to TSP?

122 Views Asked by At

Given a complete, weighted graph as the input to TSP, is the edge from $i$ to $j$ with minimum weight always in the solution?

2

There are 2 best solutions below

0
On BEST ANSWER

Try this example. If you use edge $(1,2)$, then you must also use $(3,4)$.

enter image description here

0
On

Consider the four points $P(-2,0)$, $Q(0,1)$, $R(2,0)$, $S(0,-1)$ with edges weighted by the Euclidean distance. The shortest edge is $QS$ of length $2$, and a shortest circuit containing the edge $QS$ is $PQSRP$ of length $6+2\sqrt5\approx10.47$, but the shortest circuit of all is $PQRSP$ of length $4\sqrt5\approx8.94$.