CODEWITHSUNDEEP
algorithmgraph-algorithmtraveling-salesman
user3087959
user3087959

Reputation: 11

traveling salesman without return and with given start and end cities

I am looking for the name of the following problem: traveling salesman problem (visit each city exactly once) but without returning to the start city and with visiting a given city at the end. In other words, I would like to specify the start and end cities, and I don't want to go back to the start city. Thanks!!!

Upvotes: 1

Views: 3021

Answers (2)

xagyg
xagyg

Reputation: 9711

The problem you're describing, where you want to visit each city exactly once, with a specified start and end city, and without returning to the start city, is commonly known as the "Open Traveling Salesman Problem" (Open TSP). In the standard Traveling Salesman Problem (TSP), the objective is to find the shortest possible route that visits each city exactly once and returns to the starting city. The Open TSP relaxes the requirement of returning to the starting city, allowing for a different ending city.

Upvotes: 0

Sneftel
Sneftel

Reputation: 41454

I doubt this has its own name, as it's trivially isomorphic to the normal TSP.

  • From standard TSP to this: Given a directed weighted graph for TSP, with a start/end node, split the start/end node into a start node and an end node, with all the outgoing edges on the start node and all the incoming edges on the end node.
  • From this to standard TSP: Remove all outgoing edges from the end node; add a single edge from the end node to the start node (which is now the start/end node).

Upvotes: 8

Related Questions