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 node (must pass through all nodes in S), not the other nodes. The cycle starts and ends from node w in set S.

Is it possible to delete the nodes in the set of V - S and also delete their corresponding connected edges, and then apply an algorithm (for finding the shortest cycle) to this graph, including only S nodes and their corresponding edges?

I emphasize that we only consider the nodes in set S, not the other nodes.

I am not sure if the below link is relevant to my question. The link asks for the shortest cycle that must pass through the blue nodes, but the cycle may pass through the black ones (I am not sure about this).

Finding shortest circuit in a graph that visits X nodes at least once

CodePudding user response：

Yes, the way your problem is stated, the consider approach is correct.

A graph where you remove all vertices that don't belong to a set S is called an induced subgraph. Every path/cycle in the original graph that only uses vertices from S can be found in the induced subgraph, too. Therefore, finding the shortest cycle in the induced subgraph is equivalent to finding the cycle in the original graph.

If your problem requires to find the shortest cycle that uses all nodes in S, then you're solving the travelling salesman problem, which is known to be NP-hard, which means there is no known (and likely no existing) polynomial algorithm. That said, it is a well studied problem, you can choose from both exact algorithms (if the set is small enough) and heuristics/approximations for larger scale.

CodePudding user response：

The first step is to detect the cycles that are present in your graph, if any

This can be done by modifying a depth first search ( DFS ) as follows:

- As the DFS proceeds through nodes, store the predecessor of each node visited
- IF a node is visited for the second time ( indicating cycle )
    - Back track through the node predeccessors, storing the reversed cycle

Now you can filter the cycles detected for your criteria ( visit nodes in S, shortest, etc )

Here is the C code for a DFS that detects and records cycles

void cGraph::dfs_cycle_detector(vertex_t start)
{
    std::vector<bool> visited(vVertex.size(), false);
    vVertex_t pred(vVertex.size(), 0);

    std::stack<vertex_t> wait;
    wait.push(start);

    while (!wait.empty())
    {
        vertex_t v = wait.top();
        wait.pop();
        int vi = findIndex(v);
        if (!visited[vi])
        {
            visited[vi] = true;

            for (vertex_t w : adjacentOut(v))
            {
                if (!visited[findIndex(w)])
                {
                    wait.push(w);
                    pred[findIndex(w)] = v;
                }
                else
                {
                    // previously visited node - a cycle
                    vVertex_t cycle;

                    cycle.push_back(w);
                    cycle.push_back(v);

                    vertex_t pv = pred[findIndex(v)];
                    cycle.push_back(pv);
                    while (pv != w)
                    {
                        // back track one hop
                        pv = pred[findIndex(pv)];
                        cycle.push_back(pv);
                    }

                    std::reverse(cycle.begin(), cycle.end());

                    // display cycle
                    std::cout << "cycle: ";
                    for (vertex_t vc : cycle)
                        std::cout << vc->userName() << " ";
                    std::cout << "\n";
                }
            }
        }
    }
}

The complete application for this is at https://github.com/JamesBremner/graphCycler

Example output:

node a linked to b x
node b linked to c
node c linked to d
node d linked to a
node x linked to y
node y linked to

cycle: a b c d a