-1

Consider a weighted directed graph, including V vertices and E edges. I am looking for an algorithm that finds the shortest cycle that passes through only S certain nodes at least once (must pass through all nodes in S), not the other nodes (V-S). The cycle starts and ends from node w in set S.

A similar question is asked in the below link, but in the above question, the cycle is permitted to pass through all S nodes at least once, while in the below link, the cycle must pass through all S nodes exactly once.

What is the algorithm for finding such a cycle?

Find the shortest cycle in a positive weighted directed graph passing through only specific nodes (not the other nodes)

AmirHosein Adavoudi
  • 117
  • 6
  • 1
    Start by throwing away vertices you do not want to pas through. When you finish, read [this](https://or.stackexchange.com/questions/5555/tsp-with-repeated-city-visits). – n. m. could be an AI Jan 06 '23 at 09:03
  • 2
    Please stop posting duplicate questions about your problem, especially when people are actively trying to understand exactly what you are asking and trying to help you. – beaker Jan 06 '23 at 15:33

1 Answers1

1

This is a travelling salesman problem where nodes can be revisited.

Here is the algorithm

* remove nodes and associated edges that are not in S
* Loop N over nodes
   * Construct a spanning tree for the graph starting at N
   * Connect leaf nodes of spanning tree
   * LOOP P over leaves of spanning tree
        * Mark P visited
        * set v = P
        * While nodes remain unvisited
            * Set w to connected unvisited node nearest to v
            * IF w does not exist 
                * Set w to nearest reachable node on spanning tree
                * Increment visits to nodes on path between v and W, excluding v and w
            * Mark w visited
            * Set v to w
        * Set L to length of path found
        * IF L < bestL
           * Set bestL = L
           * Set bestPath to current path
        * IF bestL == number of nodes - 1 break out of all loops
* Find shortest path from end of bestPath back to beginning

You can check a C++ implementation of a slightly different algorithm that minimizes the number of nodes revisited, used to find a route around obstacles, here https://github.com/JamesBremner/obstacles

ravenspoint
  • 19,093
  • 6
  • 57
  • 103
  • In my problem, the cycle must start from and ends at w (w is in S). May I ask you in your algorithm which node denotes the starting point? Thank you for your help. – AmirHosein Adavoudi Jan 07 '23 at 08:08
  • 1
    Look at the loop over N. This tries every starting point to find the optimal starting point. If you only want to start at one point, you can remove the loop and use a fixed N. Doing this will likely give you a result that is less optimal. You might want to consider adding a path from your starting point to the optimal starting point. You have not told us what the purpose of this is, so it is very hard to give concrete advice. – ravenspoint Jan 07 '23 at 13:39
  • I want to find the shortest cycle starting from w. Yes. you are right. In this case, the obtained cycle is not necessarily the shortest cycle with the properties said in the question. But I am looking for the shortest cycle that must start from the point w. So, removing the loop is enough for my purpose? – AmirHosein Adavoudi Jan 07 '23 at 13:55
  • 2
    Yes. But you do not need to believe me - try it for yourself. Or post a test example. – ravenspoint Jan 07 '23 at 13:58
  • May I ask you what is the base of your proposed algorithm? Is it based on DFS? – AmirHosein Adavoudi Jan 07 '23 at 15:45
  • 1
    It is based on the spanning tree algorithm. – ravenspoint Jan 07 '23 at 15:54
  • Could you please help me with your algorithm's computational complexity? It should by similar to the typical algorithms for solving TSP, which is NP-hard. Am I right? – AmirHosein Adavoudi Jan 09 '23 at 09:28
  • 1
    If you send me an example problem I can tell you how long it takes to be solved. – ravenspoint Jan 09 '23 at 15:08
  • I meant the computational complexity in terms of the main instructions, which are run on the CPU, not just for a concrete example. Is the complexity polynomial? – AmirHosein Adavoudi Jan 09 '23 at 15:37
  • 1
    Why are you so reluctant to provide a real example? Is this nothing more than an academic exercise? – ravenspoint Jan 09 '23 at 15:39
  • Since there might be more than one shortest cycle (all with the same summation of weights), may I ask you if your above algorithm returns all possible shortest cycles or just the first found one? In case your algorithm just returns one of the cycles, how should I modify your algorithm to satisfy my need? Thank you. – AmirHosein Adavoudi Jan 10 '23 at 16:10
  • 1
    It returns all the cycles found. Look at the method documentation https://github.com/JamesBremner/graphCycler/blob/45a56a27eeafa0cbe1eabcb51558f8f07525d280/src/cGraph.h#L118-L124 – ravenspoint Jan 10 '23 at 16:13
  • 1
    You should also check the unit test for multiple cycle detection https://github.com/JamesBremner/graphCycler/blob/45a56a27eeafa0cbe1eabcb51558f8f07525d280/src/test.cpp#L81-L89 – ravenspoint Jan 10 '23 at 18:33
  • Could you please explain what you mean by "Length" in "Set L to length"? – AmirHosein Adavoudi Jan 11 '23 at 15:40
  • Could you please explain how the parameter R is changed in your pseudo-code? – AmirHosein Adavoudi Jan 11 '23 at 15:41
  • 1
    You requested the shortest path - Length is the length of the path. – ravenspoint Jan 11 '23 at 15:50
  • 1
    Typo, sorry. R should be bestL – ravenspoint Jan 11 '23 at 15:51
  • Could you please explain what the line code "Increment visits to nodes on path between v and W, excluding v and w" means in the pseudo-code? Do you mean we should increase the number of times a node is visited? Could you please elaborate more on this? – AmirHosein Adavoudi Jan 11 '23 at 17:05
  • 1
    Yes. v and w are the end points between which the jump to nearest reachable takes place. They are on the spanning tree and so will be marked visited in the normal course of traversing the tree. – ravenspoint Jan 11 '23 at 17:59
  • 1
    Edges are added to the path and nodes marked visited in the method pathAdd(). I have checked in detailed documentation for this method. Hopefully it is now clearer what is happening. – ravenspoint Jan 11 '23 at 18:11
  • The complexity of your pseudo-code should not be polynomial because my problem is reduced to the TSP, which is an NP-complete problem. Am I right? Assume that after removing nodes and associated edges that are not in S, the remaining graph is complete. Could you please explain your algorithm's complexity, given this complete graph? In fact, I want to compute the worst-case complexity. – AmirHosein Adavoudi Jan 12 '23 at 08:05
  • 1
    If you send me an example problem I can tell you how long it takes to be solved. – ravenspoint Jan 12 '23 at 13:39
  • I just want to compute the complexity theoretically in a general manner, not for one specific example. I have no a real example. May I ask you kindly what you mean exactly by an example? Thank you in advance for your understanding. – AmirHosein Adavoudi Jan 12 '23 at 14:42
  • 1
    Are you working on solving an actual problem in the real world? An example could be a small, simple problem to which you know the answer, which would allow us to test my code. Or, an example could be an actual problem that you are trying to solve which would could use to give you an estimate of the actual performance. – ravenspoint Jan 12 '23 at 14:56
  • Based on the below link, your proposed pseudo-code would be incorrect. https://math.stackexchange.com/questions/4622214/the-complexity-of-a-variant-algorithm-for-the-travelling-salesman-problem-tsp/4622224?noredirect=1#comment9747769_4622224 – AmirHosein Adavoudi Jan 20 '23 at 12:26
  • I am always ready to test my code on any input you would like to provide. – ravenspoint Jan 20 '23 at 13:50