Suppose I have a directed graph, where it begins with a start node and ends with a end node. For each intermedia node, it has a type. There are directed edges defined in the nodes (not between every node pairs) with different distances. My problem is: how to find out a shortest path which “passes each type of node for at least once''? Is it a well-known problem, or any kind of variants of travelling salesman problem?
Variants of travelling salesman problem: must visit each “type” of city for at least once.
algorithmsgraph theory
Best Answer
This variant is known as the Set TSP, as well as several other names mentioned in the link.
The first reference (Noon and Bean, 1993) describes a transformation in which each set/type is visited exactly once but mentions that Noon's dissertation [10] shows how to handle intraset arcs.