1

I have related graph. Each edge has some cost. I need to find path that visit each node(possible not once) and has the least cost. Path should start and finish in same node. Is this problem described? This is not Travelling Salesman Problemm as node can be visited more than once.

Victor Semeniuk
  • 107
  • 8
  • It's an alternative version, doesn't mean that it is not *the common* traveling salesman. To continue the analogy: the salesman has repeating business some cities – OneCricketeer Jun 09 '17 at 12:01
  • Similar question https://stackoverflow.com/questions/1458048/variation-of-tsp-which-visits-multiple-cities – DAle Jun 09 '17 at 12:03

1 Answers1

1

Based on your question, I am not sure which of the following situations you are describing:

  1. The salesman must visit every node a certain number of times, and that number may be greater than 1 (and may be different for different nodes).
  2. The salesman may visit each node more than once (but does not have to), and the network is a complete network (there is an edge between every pair of nodes).
  3. The salesman may visit each node more than once and the network is not complete.

Case 1

In this case, make duplicate copies of each node -- if a node must be visited 3 times, then you'll have 3 copies of it, all located at the same place. Presumably you must depart the node in between visits (you can't visit it 3 times all in a row), in which case the distance between one copy of the node and another should be infinity.

Case 2

Just solve the problem the normal way. It will never be optimal to visit a node more than once (assuming the distances are all non-negative).

Case 3

In this case I assume you must visit every node once, and then you can visit it additional times if you're just "passing through" on your way from one node to another. The approach here is to calculate the shortest-path distance between every pair of nodes and use that as the distance matrix for a standard TSP. The standard TSP won't "know" that you're visiting nodes more than once, but you can tell which nodes are visited more than once from the optimal solution and the corresponding shortest-paths.

LarrySnyder610
  • 2,277
  • 12
  • 24