Description of the problem in question:
Say I have a complete graph with positive weighted edges. 1 vertex is specified as the "end". A subset of the other vertices are designated as "start" vertices.
I want to find paths from each start vertex to the end vertex with the following conditions:
As input, each path is given a maximum number of vertices it can visit. ie a path with a max of 5 vertices can only visit 5 other vertices before going straight to the end.
Each vertex can only be visited by one path
- Each path must visit its max number of vertices, as long as there are unvisited vertices still available.
- The total combined cost of the paths should be minimized
Basically, I want to find a path from each start vertex to end vertex that hits as many other vertices as possible, limited by each paths max and that each vertex can only be visited once. So it's possible that not all vertices will be hit or that a path won't visit its max number of vertices.
I want to know if and how this problem breaks down into TSP, or some other problem. In general, I want to figure out how to solve this problem but I'm just looking for a place to start.
Any insight would be greatly appreciated.
Thanks a lot