Problem: Find the 'shortest cycle in undirected weighted graph which contains every node'. All weights are positive. A node may be visited more than once, the is distinguishes the problem from a Hamiltonian cycle (TSP).

A naïve attempt might be to use the minimum spanning tree (MST) and backtrack to get to the starting node. This results in a length of 2*MST but is not the minimum cycle.

Example: Consider a complete graph with vertices 1,2,3,4 and edge costs c12=c13=c14=1 and c23=c24=c34=100. TSP distance = 202 (1 -> 2 -> 3 -> 4 -> 1). Shortest cycle distance = 6 (1 -> 2 -> 1 -> 3 -> 1 -> 4 -> 1)

Edit: I am looking for an algorithm to find the shortest cycle.

CodePudding user response：

In the Wikipedia page on TSP, it mentions a special case called "metric TSP", in which distances satisfy the triangle inequality.

In metric TSP, it does not matter whether or not you can visit the same city twice, because doing so is never necessary. You can always easily remove all the repeated visits without making your path any longer.

Every instance of "metric TSP" is, therefore, an instance of your problem. Metric TSP is still NP-hard, so your problem is too.