Searching for a minimum cycle in a graph containing a set of nodes-CodePudding

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.

CodePudding user response：

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.

Greedy solution

Set the starting node p_start = P[0]
set the Graph G(v,e)with nodes v and edges e
From the stating node p_start, run Dijkstra's algorithm until all the nodes in the set P are reached
Save the shortest path out af all the possible paths from p_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]
Remove P[ii] from the set P and remove the edges from e
Return to step 3. until the set p is empty

Explenation

As 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.

Solution suggestion

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

Explenation

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.

CodePudding user response：

I think what you're referring to is a minimum spanning tree. It calculates the minimum total edge weight in order to connect every vertex in the graph. There are two main algorithms to implement a MST (minimum spanning tree. One is Prim's Algorithm, and one is Kruskal's algorithm. I suggest you look into both these solutions, however in your question you mentioned that you have an initial starting vertex P[0], in which case I would recommend you looking into Prim's algorithm.