sam wrote: > Greetings! > > I have problems on the "open path" traveling salesman problem. > That is, given a starting point s, an end point d, accompained with n > points, to find the shortest path from s to d and all the n cities > (just once). > > > Is this a variation of TSP ?
If your graph is directed (ATSP), remove all out-edges from 'd', and then add a zero-cost edge from d to s and solve as any other ATSP. If your graph is undirected (STSP) add a fake city, f, between s and d. Give f only two edges, both zero cost, one each to s and d. The TSPLIB format for STSP problems supports "forced edges", which are treated as required, and zero cost, between a pair of cities. So if your original problem is, for instance, a euclidean TSP, you can say that the d-s edge is forced, and feed it to an existing TSPLIB solver. HTH --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
