HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What TSP variant doesn't return to start point?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
tspvariantwhatpointreturndoesnstart

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#43549, answer score: 6

Revisions (0)

No revisions yet.