1
$\begingroup$

This is the form of the problem where you start at a city, visit every other city, and return to the start city. Since you "return" to every city in the completed cycle, it seems intuitive that the cycle would be the same regardless of the starting city.

$\endgroup$

2 Answers 2

2
$\begingroup$

From an intuitive standpoint, no matter where you start on the path, the length of the whole path will remain the same.

More formally:

Suppose you have a valid solution to TSP for a given graph: that is, an ordering $a,b,c,d \cdots j,k,l,m \cdots x,y,z,a$ that contains every vertex and has the minimum length. Let $k$ be an arbitrary vertex in this sequence. (I've named them in alphabetical order for convenience, but of course there might be more or less than 26, depending on the graph.)

We know that the length of this cycle is the same as the length of the path $a,b \cdots j,k$ plus the length of the path $k,l \cdots y,z,a$ (by the definition of path length).

Now, let's change the cycle to start and end at $k$ instead. In other words, make a new cycle $k,l \cdots y,z,a,b \cdots j,k$. By the definition of path length, the length of this cycle is the length of $k,l \cdots y,z,a$ plus the length of $a,b \cdots j,k$. All we've done is changed the order of these two sub-paths within the cycle.

Since addition is commutative, the length of the cycle starting and ending at $a$ must be the same as the length of the cycle starting and ending at $k$. So, since $k$ is an arbitrary vertex, the length must be the same no matter which vertex you start and finish at.

EDIT: The question was clarified, so here's a better explanation of the part you're looking for.

Suppose you can get a shorter cycle by starting and ending at some arbitrary node $k$. By using the technique above, you can show that this shorter cycle can be converted to a cycle of equal length starting and ending at $a$.

But the assumption was that your original cycle was the shortest: otherwise it wouldn't be a solution to the TSP. Contradiction!

$\endgroup$
5
  • $\begingroup$ Thanks. I was actually thinking more about how to prove that starting/ending at "k" wouldn't allow you to find a different (and shorter) cycle than starting and ending at "a". But I think the answer is simply that since the path starting and ending at "a" can also be considered a path starting/ending at "k", then if there were a shorter path starting/ending at "k", then that path would also be shorter for the path starting/ending at "a". $\endgroup$ May 27, 2018 at 4:44
  • $\begingroup$ @JayCrosley Indeed! You can run the argument in reverse for that: if you have a shorter path starting/ending at $k$, then you can turn that into a path starting/ending at $a$ with the same length, but your original path was the shortest by definition, so you've got a contradiction. $\endgroup$
    – Draconis
    May 27, 2018 at 4:48
  • $\begingroup$ Nice, proof by contradiction! That's the actual method I'm looking for. $\endgroup$ May 27, 2018 at 4:51
  • $\begingroup$ @JayCrosley Yep! Added that to the answer itself $\endgroup$
    – Draconis
    May 27, 2018 at 4:53
  • $\begingroup$ If there are two or more cycles of minimal length, an algorithm might find different cycles depending where you start. Unless it is to return all cycles of minimal length, which might be an exponential number. $\endgroup$
    – gnasher729
    May 27, 2018 at 7:06
3
$\begingroup$

The optimal tour visits all vertices so it's still a tour regardless of where you start. The length of the tour is the sum of the lengths of its edges. Addition is commutative and associative so it doesn't matter what order you do the addition.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.