Why does Travelling Salesman Problem pose the restriction that each vertex can only be visited once?

According to the wiki page of TSP as a graph problem,


It is a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once

Then what if a triangle is given, with two edges weighed $1$ and the third weighed $100$,obviously, the shortest path to visit all three vertices are passing the two $1$-weighed edges twice.

So what's the meaning of such a restriction?

This mostly comes down to what makes an interesting problem, and what can be easily analyzed.

The restriction of visiting each vertex once is common in these sorts of problems. A traversal that visits each vertex no more than once is called a "path", and these are well-studied in graph theory, so there are quite a few existing theorems based on them.

The version where you can visit vertices more than once can be readily reduced to the version where you can't (and in poly-time): for every pair of nodes, calculate the shortest distance between them, remove the edge directly between them (if any), and add an edge between them with weight equal to that shortest distance. (In your example graph, this would replace the 100 edge with a 2.)

So your modified version both doesn't play into existing graph theory problems, and can be easily reduced to the standard one. It's easier just to analyze the standard one instead.

TL;DR: It's because of precedent in graph analysis. See also the Hamiltonian cycle problem, which is very closely related, and the longest path, which is a bit more distantly related.

StackExchange Computer Science Q#93895, answer score: 6