I am looking for the name of the following two problems, and an approach to solve them.
Problem#1: given N nodes, find the shortest path starting at a given start node and ending at a given end node, and passing through each node exactly once. The difference with the basic travelling salesman problem is that there is no return to the start city, and the end city is given.
Problem#2: similar to problem#1 but with "pairs" of nodes (or cities). Assume we have N pairs of nodes (so 2N nodes in total). The "pair" constraint means that if the path reaches a certain node, then the next node of the path is necessarily its pair node. For example, imagine the following pairs of cities: Berlin/Rome, Washington/Seattle, Beijing/Seoul and London/Paris. If the path goes through Berlin, then the next node on the path must be Rome. Similarly, if the path goes through Rome, then the next node must be Berlin. Given the start node Washington and the end node Paris, a "valid" path is Washington-Seattle-Seoul-Beijing-Rome-Berlin-Londong-Paris for example. Given N pairs of nodes, a start node and an end node, find the shortest path passing through each city exactly once and verifying the "pair" constraint.
Thanks!
Jean
Best Answer
If you are interested in exact solutions, and you are not in a geometric setting (i.e., no triangle inequality), you can just add a very large constant to each of the non-pairs, and solve the regular traveling salesman problem. This constant will force you to use all the pair edges (1 in the first problem, n in the second), and since the number of times you use non-pair edges is fix, it gives you an optimal solution.