If i have an undirected weighted graph G = (V, e) and a set of nodes P, how do i find the minimum cycle containing all the nodes in P?
I have a large graph G and a set of nodes P based on user input. After I get the user input i want to find the shortest path on G containing all the nodes in P.
There is a constant starting/ending node which will always be located at P[0].
I think this could be some modification of the traveling salesmen problem, which finds the shortest path including all vertices.
I can think of two propositions, one is based on a greedy algorithm that might give you a path and another that should give you the best path if one exists.
p_start = P[0]G(v,e)with nodes v and edges ep_start, run Dijkstra's algorithm until all the nodes in the set P are reachedp_start to any of the other nodes in the set p. Let us note the shortest path as the path from p_start to the node P[ii]P[ii] from the set P and remove the edges from ep is emptyAs I said, this solution is greedy as it saves the shorest path from the start to any of the candidate nodes in the set P. This solution might not reutrn an answer even though an answer might exist since the solution might be taking a little longer path at certain points to successfully complete the cycle.
Now that we put the foundations, we can move to the solution I would suggest. This problem can be looked at a Self-avoiding walk problem. I have written an implementation for a solution to finding all possible paths in the self avoiding problem here, but this is more problematic. For small number of nodes, you could run the solution in the attached which is to compute all possible paths and then choose the best one out of all the paths passing at all the nodes in P. For large graphs however, I would suggest the following adaptation:
Set the starting node p_start = P[0], remove P[0] from the set
set the Graph G(v,e)with nodes v and edges e
set starting path to empty list path = []
Set state_stack to empty list []
From p_start, run Dijkstra's algorithm to the rest of the nodes in set 'P'
For ii in length('P'):
6.1. Note e_ii to be the edges chosen to connect p_start to P[ii]
6.2. Note P_ii to be the set P without P[ii]
6.3. Create a new tuple (P[ii], G(v, e\e_ii), P_ii, path + e_ii) and add to state_stack (New starting state, new graph, new must pass set, taken path so far)
Pop another state from state_line: new_state = state_stack.pop()
Set p_start = new_state[0] ; G = new_state[1] ; P = new_state[2]
Go back to step 5. until state_stack will be empty
Choose the best accumulated path
This procedure will compute the shortest path using Dijkstra's. This path will be saved and from each of the destinations, a new path will be computed to all remaining destinations etc. This algorithm will grow factorially by the size of the initial set P but will return the best solution if such a solution exists since it computes all possible permutations of visits in the set P before choosing the best permutation and returning it.