Given a set of possible starting nodes, find the smallest path that visits certain nodes and returns back

2
votes

I have a set of nodes (<= 10,000) and edges (<= 50,000) which connect all of them with some combination. That is, you can visit any node starting from any other using atleast one combination of edges. The edges have their length defined.

I am supplied a set of mustpass nodes (maximum 5). All of them have to be visited, and we can pass through them multiple times if needed. We need to start our journey from one of the nodes which are not mustpass, visit all mustpass nodes, and return back to our initial node.

We need to find the shortest distance of such a path.

Say we have 5 nodes indexed 1, 2, 3, 4, 5 and the following edges in the format node -> node : length (all undirected):

1 -> 2 : 1
1 -> 5 : 2
3 -> 2 : 3
3 -> 4 : 5
4 -> 2 : 7
4 -> 5 : 10

And the mustpass nodes are 1, 2, 3. Our shortest distance can be achieved when we start from node 5, have a path as such: 5-1-2-3-2-1-5, and hence travel a distance of 12. 12 is our desired output.

Is there an efficient way to approach this?

1
algorithmgraph-theory

1 Answers

1
votes

Here`s O(E log V) solution:

  1. Lets consider starting node as must-pass node
  2. Using Dijkstra find shortest paths between all pairs of "must-pass" nodes
  3. Now problem is reduced to Traveling Salesman Problem with 6 cities
  4. We can either check all permutations in O(6!) time or use dynamic programming for O(2^6 * 6^2) either way since 6 is a constant complexity is O(1) for this part