Given a Weighted Undirected Graph G = (V,E), and a subset S of V, How we can find a minimum cost cycle that contains every vertex of set S. You can visit every vertex & edge any number of times.
constraints: #1: weight of edges are positive #2: Size of set V is less than 100 #3: Size of set E is less than 500 #4: Each vertex of set V is reachable from every other vertex i.e. Graph G is connected.
Any insights , resources or help to solve the problems including cycles are welcomed.
Thank you very much for your help & time.
not sure if it could work but…what about dijkstra with one of the Vs of S as source and destination but allowing revisiting source only if all others Vs in S were also visited?
the elements of the priority queue could be (cost, rest, visited), where rest is the number of vertices of the set than rest to visit, and visited is a vector that keep track of the visited nodes in each path. I think it could work because the number of vertices is small