Implementation of a particular Travelling-Salesman variation

Question

I'm looking for an algorithm(C/C++/Java - doesn't matter) which will resolve a problem which consists of finding the shortest path between 2 nodes (A and B) of a graph. The catch is that the path must visit certain other given nodes(cities). A city can be visited more than once. Example of path(A-H-D-C-E-F-G-F-B) (where A is source, B is destination, F and G are cities which must be visited).

I see this as a variation of the Traveling Salesman Problem but I couldn't find or write a working algorithm based on my searches.

I was trying to find a solution starting from these topics but without any luck: https://stackoverflow.com/questions/24856875/tsp-branch-and-bound-implementation-in-c and Variation of TSP which visits multiple cities

score 1 · Accepted Answer · answered Jul 25 '14 at 13:36

1

An easy reduction of the problem to TSP would be:

For each (u,v) that "must be visited", find the distance d(u,v) between them. This can be done efficiently using Floyd-Warshall Algorithm to find all-to-all shortest path.
Create a new graph G' consisting only of those nodes, with all edges existing, with the distances as calculated on (1).
Run standard TSP algorithm to solve the problem on the reduced graph.

answered Jul 25 '14 at 13:36

amit

175,853
27
231
333

Hmm, this could be a great solution. I'm not sure at step 3 though, as each node can be visited multiple times and the standard TSP algorithm visits only once. Maybe I'm wrong and it actually gives the shortest path, I'll have to write the implementation to check, thank you! – Feri Csokatu Jul 25 '14 at 13:50

score 0 · Answer 2 · edited Jul 28 '14 at 18:08

I think that in addition to amit's answer, you'll want to increase the cost of the edges that have A or B as endpoints by a sufficient amount (the total cost of the graph + 1 would probably be sufficient) to ensure that you don't end up with a path that goes through A or B (instead of ending at A and B).

A--10--X--0--B
|      |     |
|      10    |
|      |     |
+---0--Y--0--+

The above case would result in a path from A to Y to B to X, unless you increase the cost of the A and B edges (by 21).

A--31--X--21--B
|      |      |
|      10     |
|      |      |
+---21--Y--21-+

Now it goes from A to X to Y to B. Also make sure you remove any edges (A,B) (if they exist).

Implementation of a particular Travelling-Salesman variation

2 Answers2

Linked