0

I have a weighted directed graph G, including the vertices V and edges E. I have certain nodes, namely S, which are the subset of the set V. Among the nodes in S, one of them is considered as the starting point, namely, t.

How can I find the shortest cycle that starts from t, passes through the nodes in S, and ends at t? I am wondering if the starting point plays an important role in our problem.

I saw a similar question asked before in the below link, but the question in the link says that the cycle passes through at list one of the nodes in the set U, which in our case is the set S. In fact, in my case the cycle must pass through all the nodes in the set U or in my case set S. Finding the lightest path to one vertex from all others in a graph

A similar question in the below link asks for the path, not the cycle I am looking for. Find the shortest path in a graph which visits certain nodes

A similar question in the below link concerns an undirected graph, while in my case, the graph is directed. Finding shortest circuit in a graph that visits X nodes at least once

AmirHosein Adavoudi
  • 117
  • 6
  • I should emphasize that the cycle must pass through all the nodes in set S. – AmirHosein Adavoudi Jan 01 '23 at 17:56
  • Then it is like a traveling salesman problem. NP-complete. – trincot Jan 01 '23 at 17:57
  • The set S is the subset of the set V. Even in this case, my problem is like a traveling salesman's problem? – AmirHosein Adavoudi Jan 01 '23 at 18:06
  • Consider you could derive a new graph G' that only has the vertices in S. If there were vertices u and v in S, and w1, w2, ... wn not in S, such that u-w*-v would be the shortest path from u to v in G, then we could add that as a direct edge u-v in G' with that particular weiight. Now you have mapped the original problem to a problem where S=V. – trincot Jan 01 '23 at 18:13

0 Answers0