Search code examples
javac++algorithmtraveling-salesman

Implementation of a particular Travelling-Salesman variation

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

Solution

  • An easy reduction of the problem to TSP would be:

    1. 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.
    2. Create a new graph G' consisting only of those nodes, with all edges existing, with the distances as calculated on (1).
    3. Run standard TSP algorithm to solve the problem on the reduced graph.