For my case I have starting point and several cities.

I want the shortest route to visit all cities without returning starting point.

I have read several TSP algorithm and all include the return a full cycle.

So what TSP variation should I look for to solve my problem?

• Look at Hamiltonian path.
– Juho
Commented Jun 12, 2015 at 22:02
• In the worst case, you can solve this by solving ordinary TSP $n-1$ times. This is because a solution to your problem is a solution to TSP where the cost from the last city back to the start is zero. The problem is that you don't know which city is supposed to come last, but you can try each one in turn. Commented Jun 13, 2015 at 10:34
• Compute TSP three times: once with the cost of Ab set to zero, once with Ac (and Ab put back to its real cost) and once with Ad (and Ab and Ac at their real costs). The smallest answer is the answer to your question. Commented Jun 13, 2015 at 12:56
• @DavidRicherby I don't agree with that at all. From a theoretic point of view, yes, this is not much worse. However, from a practical point of view, it matters all the more because solving TSP is already slow enough, so you have to do everything you can. (In easier problems, you can have a suboptimal algorithm that is still fast enough for your purpose, but if solving one instance of the problem may take several hours, you have to be on your toes.) Then again, practical issues are not within the scope of this site, so I suppose you are right. ;-) Commented Jul 25, 2017 at 17:00
• In particular, it is not clear whether your graph is directed or undirected, weighted or unweighted, complete or general, whether the path you're looking for has to be simple (may not visit a city more than once), and whether or not there are constraints on the start and/or end vertex of the desired path. Commented Jul 25, 2017 at 23:59

You can reduce to a normal TSP variant by adding a dummy city that is distance $0$ away from each of the existing cities. (See also this answer on StackOverflow.)

Edit: it seems that my suggested modification is not quite appropriate: as I understand it, your Hamiltonian path has a fixed starting point but no fixed end point. One way to solve this is to add two dummy cities $v$ and $w$ such that:

• $v$ is only connected to the starting point and to $w$,
• $w$ is connected to everything.

Turn it into an instance of the Hamiltonian $s-t$ path problem, as suggested in the comments of your original post.

Take your input graph and add two new vertices $s$ and $t$. Both of them should be connected to all other cities, but not to one another. All edges incident to $s$ or $t$ should be weighted 0.

Your 'salesman' can then start at $s$, visit all cities included on the original graph, and finish up at $t$.

• Hm. The Hamiltonian path problem is unweighted, whereas OP clearly speaks of a shortest route (and you also speak of weights). That's why I'm reducing the problem to an instance of TSP. Furthermore, I see no reason why a Hamiltonian path in your extended graph should start in $s$ and finish in $t$. It can do so, yes, but there is no guarantee that an arbitrary Hamiltonian path in your graph has this property. Commented Jul 25, 2017 at 23:15
• Oh, right, you're reducing it to the Hamiltonian $s$-$t$-path problem. Is that even a thing? Is there a special algorithm for the Hamiltonian path problem that assumes knowledge of the start and end points? Commented Jul 25, 2017 at 23:19
• Yeah it's a thing if you want it to be I guess... mathworld.wolfram.com/HamiltonianPath.html . I may have made an incorrect assumption in thinking the input graph OP had in mind was complete. In the case that it was complete and a direct route between all cities existed, we can just add edge weights and turn it into a Hamiltonian shortest path problem. Whilst I'm struggling to find any research papers specifically addressing this variant, I'd hazard a guess that since the equivalent decision problem is known to be NP-complete, there's probably a good chance this optimisation variant is Commented Jul 25, 2017 at 23:41
• NP-hard. I will do some digging and see if I can find anything backing it up. Since you probably wont be able to find a polynomial time algorithm solving this, I guess an approximation algorithm (researchgate.net/publication/…) or some sort of heuristic approach are OPs best bets. Commented Jul 25, 2017 at 23:43
• Okay, it seems that the question is missing details. :-) In any case, most variants of the Hamiltonian shortest path problem can be proven to be NP-hard by reductions from TSP, similar to the one I describe here. (General procedure: duplicate one vertex, add seperate degree-one vertices to each of the two copies.) I deliberately left out a proof that the problem was NP-hard, because the OP only asked for a reduction from his problem to TSP, not the other way around. Commented Jul 25, 2017 at 23:53